| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 101179 |
2019-03-17T08:26:44 Z |
E869120 |
Wall (CEOI14_wall) |
C++14 |
|
1694 ms |
43228 KB |
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <tuple>
using namespace std;
long long dist[44][44][1024];
int H, W, P[1009][1009], A[1009][1009], B[1009][1009];
int cp[44][44][4], cq[44][44][4];
vector<pair<int, int>>L;
int main() {
cin >> H >> W;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) { cin >> P[i][j]; if (P[i][j] >= 1) L.push_back(make_pair(i, j)); }
}
for (int i = 0; i < H; i++) {
for (int j = 0; j < W + 1; j++) {
cin >> A[i][j];
cq[i][j][1] = A[i][j]; cq[i + 1][j][3] = A[i][j];
}
}
for (int i = 0; i < H + 1; i++) {
for (int j = 0; j < W; j++) {
cin >> B[i][j];
cq[i][j][0] = B[i][j]; cq[i][j + 1][2] = B[i][j];
for (int k = 0; k < L.size(); k++) {
if (L[k].second == j && L[k].first >= i) { cp[i][j][0] += (1 << k); cp[i][j + 1][2] += (1 << k); }
}
}
}
for (int i = 0; i <= H; i++) { for (int j = 0; j <= W; j++) { for (int k = 0; k < 1024; k++) dist[i][j][k] = (1LL << 60); } }
priority_queue<tuple<long long, int, int, int>, vector<tuple<long long, int, int, int>>, greater<tuple<long long, int, int, int>>>Q;
dist[0][0][0] = 0; Q.push(make_tuple(0, 0, 0, 0));
while (!Q.empty()) {
tuple<long long, int, int, int> tup = Q.top(); Q.pop();
int px = get<1>(tup), py = get<2>(tup), mask = get<3>(tup);
int sx[4] = { 0, 1, 0, -1 }, sy[4] = { 1, 0, -1,0 };
for (int i = 0; i < 4; i++) {
int tx = px + sx[i], ty = py + sy[i];
if (tx < 0 || ty < 0 || tx > H || ty > W) continue;
int mask1 = (mask ^ cp[px][py][i]);
long long cost = cq[px][py][i];
if (dist[tx][ty][mask1] > dist[px][py][mask] + cost) {
dist[tx][ty][mask1] = dist[px][py][mask] + cost;
Q.push(make_tuple(dist[tx][ty][mask1], tx, ty, mask1));
}
}
}
cout << dist[0][0][(1 << L.size()) - 1] << endl;
return 0;
}
Compilation message
wall.cpp: In function 'int main()':
wall.cpp:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < L.size(); k++) {
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1408 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1536 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1536 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1280 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1536 KB |
Output is correct |
| 6 |
Correct |
11 ms |
8064 KB |
Output is correct |
| 7 |
Correct |
608 ms |
10516 KB |
Output is correct |
| 8 |
Correct |
21 ms |
8640 KB |
Output is correct |
| 9 |
Correct |
8 ms |
5888 KB |
Output is correct |
| 10 |
Correct |
10 ms |
8152 KB |
Output is correct |
| 11 |
Correct |
1120 ms |
16140 KB |
Output is correct |
| 12 |
Correct |
50 ms |
13056 KB |
Output is correct |
| 13 |
Correct |
247 ms |
17644 KB |
Output is correct |
| 14 |
Correct |
1236 ms |
19516 KB |
Output is correct |
| 15 |
Correct |
13 ms |
10880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
26744 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Incorrect |
1049 ms |
16316 KB |
Output isn't correct |
| 3 |
Incorrect |
716 ms |
26680 KB |
Output isn't correct |
| 4 |
Correct |
17 ms |
13696 KB |
Output is correct |
| 5 |
Runtime error |
34 ms |
27512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
34 ms |
27520 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
34 ms |
28836 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Incorrect |
863 ms |
15600 KB |
Output isn't correct |
| 9 |
Correct |
156 ms |
15212 KB |
Output is correct |
| 10 |
Correct |
23 ms |
14784 KB |
Output is correct |
| 11 |
Runtime error |
42 ms |
27568 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
31 ms |
27384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
36 ms |
28152 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Correct |
1198 ms |
16248 KB |
Output is correct |
| 15 |
Correct |
172 ms |
17104 KB |
Output is correct |
| 16 |
Correct |
18 ms |
14840 KB |
Output is correct |
| 17 |
Runtime error |
44 ms |
27552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
37 ms |
27484 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
88 ms |
36584 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
76 ms |
35972 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
72 ms |
36336 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
74 ms |
36252 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
1694 ms |
40116 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
95 ms |
36600 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
130 ms |
39616 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
104 ms |
39192 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
149 ms |
39800 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
163 ms |
39704 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
188 ms |
40056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
182 ms |
36728 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
274 ms |
39552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
626 ms |
41848 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
185 ms |
41720 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
221 ms |
42844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
223 ms |
43128 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
199 ms |
43228 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
288 ms |
42232 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
519 ms |
42628 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
