Submission #19174
Source Code Expand
Copy
#include <iostream> #include <cstdio> #include <vector> #include <string> #include <queue> #include <map> #include <set> #include <cmath> using namespace std; const int di[] = {+1,-1, 0, 0}; const int dj[] = { 0, 0,+1,-1}; int N, M; vector<string> s; bool visited[500][500]; bool visit(int i, int j) { if (!(0 <= i && i < N && 0 <= j && j < M)) return false; if (s[i][j] == '#') return false; if (s[i][j] == 'g') return true; if (visited[i][j]) return false; visited[i][j] = true; for (int k = 0; k < 4; ++ k) { if (visit(i+di[k], j+dj[k])) return true; } return false; } int main() { cin >> N >> M; s= vector<string>(N); int si = 0, sj = 0; int gi = 0, gj = 0; for (int i = 0; i < N; ++ i) { cin >> s[i]; for (int j = 0; j < M; ++ j) { if (s[i][j] == 's') { si = i; sj = j; } if (s[i][j] == 'g') { gi = i; gj = j; } } } if (!visit(si, sj)) { cout << -1 << endl; return 0; } vector<vector<double> > a(N, vector<double>(M, 0)); a[si][sj] = 1e+300; set<pair<int,int> > b; b.insert(make_pair(si,sj)); double ans = 0; for (int t = 1; !b.empty(); ++ t) { vector<vector<double> > a0 = a; set<pair<int,int> > c; for (set<pair<int,int> >::iterator it = b.begin(); it != b.end(); ++ it) { int i = it->first; int j = it->second; for (int k = 0; k < 4; ++ k) { int ii = i + di[k]; int jj = j + dj[k]; if (!(0 <= ii && ii < N && 0 <= jj && jj < M)) continue; if (s[ii][jj] == '#') continue; double x = a0[i][j]; if ('1' <= s[ii][jj] && s[ii][jj] <= '9') { x = min(x, (s[ii][jj]-'0')*pow(0.99, t)); } if (x > a[ii][jj]) { a[ii][jj] = x; c.insert(make_pair(ii, jj)); } } } ans = max(ans, a[gi][gj]); b = c; } printf("%.10f\n", ans); }
Submission Info
Submission Time | |
---|---|
Task | C - 暗闇帰り道 |
User | hasi |
Language | C++ (G++ 4.6.4) |
Score | 0 |
Code Size | 1846 Byte |
Status | RE |
Exec Time | 5034 ms |
Memory | 14584 KB |
Judge Result
Set Name | all | ||||||
---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 100 | ||||||
Status |
|
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 | 25 ms | 848 KB |
00_mini_02.txt | AC | 29 ms | 776 KB |
00_mini_03.txt | AC | 28 ms | 780 KB |
00_mini_04.txt | AC | 25 ms | 764 KB |
00_mini_05.txt | AC | 24 ms | 848 KB |
00_sample_01.txt | AC | 23 ms | 776 KB |
00_sample_02.txt | AC | 24 ms | 848 KB |
01_rnd_01.txt | AC | 483 ms | 12328 KB |
01_rnd_02.txt | AC | 207 ms | 4228 KB |
01_rnd_03.txt | AC | 81 ms | 1656 KB |
01_rnd_04.txt | AC | 102 ms | 2680 KB |
01_rnd_05.txt | AC | 44 ms | 1020 KB |
01_rnd_06.txt | AC | 31 ms | 1120 KB |
01_rnd_07.txt | AC | 86 ms | 1680 KB |
01_rnd_08.txt | AC | 299 ms | 4712 KB |
01_rnd_09.txt | AC | 504 ms | 5836 KB |
01_rnd_10.txt | AC | 410 ms | 4084 KB |
01_rnd_11.txt | AC | 258 ms | 3800 KB |
01_rnd_12.txt | AC | 155 ms | 3316 KB |
01_rnd_13.txt | AC | 42 ms | 1156 KB |
01_rnd_14.txt | AC | 326 ms | 4964 KB |
01_rnd_15.txt | AC | 152 ms | 3488 KB |
01_rnd_16.txt | AC | 110 ms | 1896 KB |
01_rnd_17.txt | AC | 33 ms | 1148 KB |
01_rnd_18.txt | AC | 26 ms | 784 KB |
01_rnd_19.txt | AC | 26 ms | 776 KB |
01_rnd_20.txt | AC | 26 ms | 780 KB |
02_maxrnd_01.txt | AC | 816 ms | 11556 KB |
02_maxrnd_02.txt | AC | 568 ms | 9576 KB |
02_maxrnd_03.txt | AC | 973 ms | 14584 KB |
02_maxrnd_04.txt | AC | 814 ms | 14064 KB |
02_maxrnd_05.txt | AC | 772 ms | 9964 KB |
02_maxrnd_06.txt | AC | 736 ms | 11608 KB |
02_maxrnd_07.txt | AC | 654 ms | 9708 KB |
02_maxrnd_08.txt | AC | 654 ms | 8200 KB |
02_maxrnd_09.txt | AC | 722 ms | 6344 KB |
02_maxrnd_10.txt | AC | 670 ms | 10756 KB |
02_maxrnd_11.txt | AC | 615 ms | 10608 KB |
02_maxrnd_12.txt | AC | 608 ms | 9528 KB |
02_maxrnd_13.txt | AC | 587 ms | 6864 KB |
02_maxrnd_14.txt | AC | 485 ms | 8076 KB |
02_maxrnd_15.txt | AC | 555 ms | 5400 KB |
02_maxrnd_16.txt | AC | 543 ms | 6480 KB |
02_maxrnd_17.txt | AC | 955 ms | 5632 KB |
02_maxrnd_18.txt | AC | 45 ms | 1236 KB |
02_maxrnd_19.txt | AC | 40 ms | 1028 KB |
03_hard_01.txt | RE | 265 ms | 11264 KB |
03_hard_02.txt | RE | 269 ms | 11352 KB |
03_hard_03.txt | TLE | 5034 ms | 13076 KB |
03_hard_04.txt | RE | 0 ms | 13072 KB |
03_hard_05.txt | RE | 275 ms | 11272 KB |
03_hard_06.txt | RE | 267 ms | 11352 KB |
03_hard_07.txt | TLE | 5033 ms | 13076 KB |
03_hard_08.txt | RE | 0 ms | 13072 KB |
04_open_01.txt | RE | 264 ms | 11260 KB |
04_open_02.txt | RE | 264 ms | 11352 KB |
05_minihard_01.txt | AC | 29 ms | 844 KB |
05_minihard_02.txt | AC | 26 ms | 888 KB |
05_minihard_03.txt | AC | 25 ms | 848 KB |
05_minihard_04.txt | AC | 25 ms | 872 KB |
05_minihard_05.txt | AC | 25 ms | 848 KB |
05_minihard_06.txt | AC | 44 ms | 784 KB |
05_minihard_07.txt | AC | 25 ms | 776 KB |
05_minihard_08.txt | AC | 30 ms | 856 KB |