Submission #19342


Source Code Expand

Copy
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int,int> pii;
typedef pair<double,pii> pdii;

int main(){
	int n, m;
	int s, gy, gx;
	char ch;
	cin >> n >> m;
	vector<vector<int> > c( n + 2, vector<int>( m + 2, -1 ) );
	for( int i = 1; i <= n; ++i ){
		for( int j = 1; j <= m; ++j ){
			cin >> ch;
			switch( ch ){
				case 's':
					s = i * 1024 + j;
					break;
				case 'g':
					gy = i;
					gx = j;
					c[i][j] = 1000000000;
					break;
				case '#':
					break;
				default:
					c[i][j] = ch - '0';
					break;
			}
		}
	}
	
	priority_queue<pdii> q[2];
	q[0].push( pdii( 100.0, pii(s, s) ) );
	double r = 0.99;
	double maxgl = -1.0;
	vector<vector<double> > maxl( n + 2, vector<double>( m + 2, -1.0 ) );
	vector<vector<bool> > check( n + 2, vector<bool>( m + 2 ) );

	int d[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };

	int t = 1;
	int z = 0;
	while( !q[z].empty() ){
		while( !q[z].empty() ){
			pdii p = q[z].top();
			q[z].pop();
			int y = p.second.first / 1024;
			int x = p.second.first % 1024;
			
			if( !check[y][x] ){
				check[y][x] = true;
				
				for( int k = 0; k < 4; ++k ){
					int ny = y + d[k][0];
					int nx = x + d[k][1];
					int np = ny * 1024 + nx;

					if( np != p.second.second && c[ny][nx] != -1 ){
						double nl = min( r * c[ny][nx], p.first );
						if( maxgl < nl && maxl[ny][nx] < nl ){
							maxl[ny][nx] = nl;
							q[!z].push( pdii( nl, pii(ny * 1024 + nx, p.second.first) ) );
						}
					}
				}
			}
		}

		if( maxl[gy][gx] > maxgl ){
			maxgl = maxl[gy][gx];
		}
		
		for( int i = 1; i <= n; ++i ){
			for( int j = 1; j <= m; ++j ){
				check[i][j] = false;
				maxl[i][j] = -1.0;
			}
		}
		
		r *= 0.99;
		++t;
		z = !z;
	}
	
	if( maxgl < 0.0 ){
		printf("-1\n");
	}
	else{
		printf("%.15f\n", maxgl );
	}
}

Submission Info

Submission Time
Task A - GPA計算
User climpet
Language C++ (GCC 4.4.7)
Score 0
Code Size 1960 Byte
Status RE
Exec Time 315 ms
Memory 812 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
RE × 32
Set Name Test Cases
all 00_sample_01.txt, 00_sample_02.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 02_rndmax_01.txt, 02_rndmax_02.txt, 02_rndmax_03.txt, 02_rndmax_04.txt, 02_rndmax_05.txt, 02_rndmax_06.txt, 02_rndmax_07.txt, 02_rndmax_08.txt, 02_rndmax_09.txt, 02_rndmax_10.txt, 03_mini_01.txt, 03_mini_02.txt, 03_mini_03.txt, 03_mini_04.txt, 03_mini_05.txt, 04_samemax_01.txt, 04_samemax_02.txt, 04_samemax_03.txt, 04_samemax_04.txt, 04_samemax_05.txt
Case Name Status Exec Time Memory
00_sample_01.txt RE 252 ms 784 KB
00_sample_02.txt RE 252 ms 792 KB
01_rnd_01.txt RE 251 ms 812 KB
01_rnd_02.txt RE 255 ms 788 KB
01_rnd_03.txt RE 248 ms 780 KB
01_rnd_04.txt RE 250 ms 784 KB
01_rnd_05.txt RE 253 ms 792 KB
01_rnd_06.txt RE 245 ms 784 KB
01_rnd_07.txt RE 268 ms 796 KB
01_rnd_08.txt RE 251 ms 784 KB
01_rnd_09.txt RE 251 ms 784 KB
01_rnd_10.txt RE 249 ms 788 KB
02_rndmax_01.txt RE 251 ms 784 KB
02_rndmax_02.txt RE 252 ms 764 KB
02_rndmax_03.txt RE 251 ms 788 KB
02_rndmax_04.txt RE 248 ms 764 KB
02_rndmax_05.txt RE 247 ms 788 KB
02_rndmax_06.txt RE 249 ms 800 KB
02_rndmax_07.txt RE 249 ms 792 KB
02_rndmax_08.txt RE 250 ms 740 KB
02_rndmax_09.txt RE 248 ms 784 KB
02_rndmax_10.txt RE 315 ms 788 KB
03_mini_01.txt RE 246 ms 784 KB
03_mini_02.txt RE 255 ms 788 KB
03_mini_03.txt RE 254 ms 796 KB
03_mini_04.txt RE 246 ms 788 KB
03_mini_05.txt RE 257 ms 788 KB
04_samemax_01.txt RE 250 ms 792 KB
04_samemax_02.txt RE 256 ms 780 KB
04_samemax_03.txt RE 243 ms 732 KB
04_samemax_04.txt RE 246 ms 788 KB
04_samemax_05.txt RE 244 ms 792 KB