Contest Duration: - (local time) (90 minutes) Back to Home

Submission #580122

Source Code Expand

Copy
```#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
#define FOR(i,a,b) for (int i=(a); i<(b); i++)
typedef pair<int,int> PII;
typedef pair<int,pair<int,int> > PIII;
typedef pair<ll,ll> PLL;

const int INF = (1<<28);

int N,M;
int c[512][512];
PII s;
int dist[512][512]; //最小コスト

int dy[] = {-1,0,1,0};
int dx[] = {0,1,0,-1};

bool f(int ny, int nx){
return (0<=ny && ny < N && 0<=nx && nx < M);
}

// 明るさl以上の経路が存在するか否か
bool check(double l){
queue<PIII> q; //時間 y x
for(int y=0;y<512;y++) for(int x=0;x<512;x++) { dist[y][x]=INF; }

q.push(PIII(0, PII(s.first, s.second)));

// BFS
while(!q.empty()){
PIII p = q.front(); q.pop();

if(dist[p.second.first][p.second.second] <= p.first) { continue; }
dist[p.second.first][p.second.second] = p.first;

//cout<<p.second.first<<":"<<p.second.second<<endl;

for(int k=0;k<4;k++){
int ny = p.second.first  + dy[k];
int nx = p.second.second + dx[k];
int nt = p.first+1;

if(f(ny,nx) && '0'<=c[ny][nx] && c[ny][nx]<='9' && (c[ny][nx]-'0')*pow(0.99,nt)>=l ){
q.push(PIII(nt, PII(ny,nx)));
}else if(f(ny,nx) && c[ny][nx]=='g'){
return true;
}
}
}

return false;
}

int main(){
cin>>N>>M;
for(int y=0;y<N;y++){
string str;
cin>>str;
for(int x=0;x<M;x++){
c[y][x] = str[x];
if(c[y][x]=='s'){
s.first = y;
s.second = x;
}
}
}

if(!check(-1.0)){
cout<<"-1"<<endl;
return 0;
}

double l=0.0, r=10.0;
while(r-l >= 1e-10){
double m = (r+l)/2;
if(check(m)){
l=m;
}else{
r=m;
}
}

printf("%.9f\n",l);
return 0;
}
```

#### Submission Info

Submission Time 2015-11-24 22:43:31+0900 C - 暗闇帰り道 bobuhiro11 C++11 (GCC 4.8.1) 100 2030 Byte AC 4787 ms 3188 KB

#### Judge Result

Set Name all
Score / Max Score 100 / 100
Status
 AC × 64
Set Name Test Cases
all 00_mini_01.txt, 00_mini_02.txt, 00_mini_03.txt, 00_mini_04.txt, 00_mini_05.txt, 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, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 02_maxrnd_01.txt, 02_maxrnd_02.txt, 02_maxrnd_03.txt, 02_maxrnd_04.txt, 02_maxrnd_05.txt, 02_maxrnd_06.txt, 02_maxrnd_07.txt, 02_maxrnd_08.txt, 02_maxrnd_09.txt, 02_maxrnd_10.txt, 02_maxrnd_11.txt, 02_maxrnd_12.txt, 02_maxrnd_13.txt, 02_maxrnd_14.txt, 02_maxrnd_15.txt, 02_maxrnd_16.txt, 02_maxrnd_17.txt, 02_maxrnd_18.txt, 02_maxrnd_19.txt, 03_hard_01.txt, 03_hard_02.txt, 03_hard_03.txt, 03_hard_04.txt, 03_hard_05.txt, 03_hard_06.txt, 03_hard_07.txt, 03_hard_08.txt, 04_open_01.txt, 04_open_02.txt, 05_minihard_01.txt, 05_minihard_02.txt, 05_minihard_03.txt, 05_minihard_04.txt, 05_minihard_05.txt, 05_minihard_06.txt, 05_minihard_07.txt, 05_minihard_08.txt
Case Name Status Exec Time Memory
00_mini_01.txt AC 50 ms 1844 KB
00_mini_02.txt AC 32 ms 1900 KB
00_mini_03.txt AC 33 ms 1904 KB
00_mini_04.txt AC 33 ms 1900 KB
00_mini_05.txt AC 26 ms 1952 KB
00_sample_01.txt AC 33 ms 1952 KB
00_sample_02.txt AC 32 ms 1892 KB
01_rnd_01.txt AC 3866 ms 2924 KB
01_rnd_02.txt AC 488 ms 2792 KB
01_rnd_03.txt AC 70 ms 2156 KB
01_rnd_04.txt AC 279 ms 2412 KB
01_rnd_05.txt AC 64 ms 2072 KB
01_rnd_06.txt AC 40 ms 2080 KB
01_rnd_07.txt AC 67 ms 2924 KB
01_rnd_08.txt AC 598 ms 2924 KB
01_rnd_09.txt AC 882 ms 2912 KB
01_rnd_10.txt AC 1177 ms 2932 KB
01_rnd_11.txt AC 608 ms 2540 KB
01_rnd_12.txt AC 374 ms 2284 KB
01_rnd_13.txt AC 113 ms 2076 KB
01_rnd_14.txt AC 1415 ms 2664 KB
01_rnd_15.txt AC 628 ms 2416 KB
01_rnd_16.txt AC 39 ms 2408 KB
01_rnd_17.txt AC 51 ms 2540 KB
01_rnd_18.txt AC 28 ms 2124 KB
01_rnd_19.txt AC 31 ms 2720 KB
01_rnd_20.txt AC 31 ms 2916 KB
02_maxrnd_01.txt AC 1012 ms 3048 KB
02_maxrnd_02.txt AC 659 ms 3048 KB
02_maxrnd_03.txt AC 1098 ms 3052 KB
02_maxrnd_04.txt AC 1924 ms 3040 KB
02_maxrnd_05.txt AC 1038 ms 3052 KB
02_maxrnd_06.txt AC 3705 ms 3052 KB
02_maxrnd_07.txt AC 304 ms 3044 KB
02_maxrnd_08.txt AC 148 ms 3044 KB
02_maxrnd_09.txt AC 3289 ms 3048 KB
02_maxrnd_10.txt AC 473 ms 3052 KB
02_maxrnd_11.txt AC 2809 ms 3056 KB
02_maxrnd_12.txt AC 1265 ms 3044 KB
02_maxrnd_13.txt AC 1689 ms 3048 KB
02_maxrnd_14.txt AC 1904 ms 3044 KB
02_maxrnd_15.txt AC 310 ms 3044 KB
02_maxrnd_16.txt AC 1353 ms 3048 KB
02_maxrnd_17.txt AC 905 ms 3056 KB
02_maxrnd_18.txt AC 46 ms 3040 KB
02_maxrnd_19.txt AC 45 ms 3052 KB
03_hard_01.txt AC 4267 ms 3044 KB
03_hard_02.txt AC 4439 ms 3048 KB
03_hard_03.txt AC 117 ms 3180 KB
03_hard_04.txt AC 138 ms 3176 KB
03_hard_05.txt AC 4315 ms 3060 KB
03_hard_06.txt AC 4402 ms 2980 KB
03_hard_07.txt AC 116 ms 3184 KB
03_hard_08.txt AC 136 ms 3188 KB
04_open_01.txt AC 4787 ms 3052 KB
04_open_02.txt AC 4544 ms 3048 KB
05_minihard_01.txt AC 46 ms 2028 KB
05_minihard_02.txt AC 46 ms 2024 KB
05_minihard_03.txt AC 40 ms 2028 KB
05_minihard_04.txt AC 42 ms 2040 KB
05_minihard_05.txt AC 44 ms 2080 KB
05_minihard_06.txt AC 49 ms 2168 KB
05_minihard_07.txt AC 39 ms 2072 KB
05_minihard_08.txt AC 40 ms 2080 KB