#include<bits/stdc++.h>
using namespace std;
#include "wombats.h"
const int M = 1000;
int T[M + 10][200][200];
int h[5010][210], v[5010][210];
int f[210][210], opt[210][210];
int r, c;
void calc (int l, int r) {
for(int i = 0; i < c; i++) for(int j = 0; j < c; j++) f[i][j] = (i == j ? 0 : 1e9);
for(int row = l; row <= r; row++) {
if (row != l) {
for(int i = 0; i < c; i++) for(int j = 0; j < c; j++) {
f[i][j] += v[row - 1][j];
}
}
for(int i = 0; i < c; i++) {
for(int j = 1; j < c; j++) f[i][j] = min(f[i][j], f[i][j - 1] + h[row][j - 1]);
for(int j = c - 2; j >= 0; j--) f[i][j] = min(f[i][j], f[i][j + 1] + h[row][j]);
}
}
}
void up (int s, int l, int r, int pos) {
// if (s == 2) cout << l << " " << r << endl;
if (s * 2 > M || r == l) {
calc(l, r);
for(int i = 0; i < c; i++) for(int j = 0; j < c; j++) T[s][i][j] = f[i][j];
return;
}
int mid = l + r >> 1;
if (pos <= mid) up(s << 1, l, mid, pos);
else up(s << 1 | 1, mid + 1, r, pos);
// for(int i = 0; i < c; i++) {
// T[s][i][i] = 2e9;
// for(int j = 0; j < c; j++) {
// int cost = T[s << 1][i][j] + v[mid][j] + T[s << 1 | 1][j][i];
// if (T[s][i][i] > cost) {
// T[s][i][i] = cost;
// opt[i][i] = j;
// }
// }
// }
for(int i = c - 1; i >= 0; i--) for(int j = 0; j < c; j++) {
T[s][i][j] = 1e9;
// if (s == 2) cout << i << " " << j << endl;
// if (s == 2 && i == 2 && j == 1) cout << 148971 << endl;
for(int k = 0; k < c; k++) {
int cost = T[s << 1][i][k] + v[mid][k] + T[s << 1 | 1][k][j];
if (T[s][i][j] > cost) {
T[s][i][j] = cost;
opt[i][j] = k;
}
// if (T[s][i][j] == 0) {
// cout << i << " " << j << endl;
// cout << l << " " << r << endl;
// exit(0);
// }
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
/* ... */
r = R;
c = C;
for(int i = 0; i < r; i++) for(int j = 0; j + 1 < c; j++) h[i][j] = H[i][j];
for(int i = 0; i + 1 < r; i++) for(int j = 0; j < c; j++) v[i][j] = V[i][j];
for(int i = 0; i < c; i++) up(1, 0, r - 1, i);
// cout << T[2][2][1];
// exit(0);
// for(int i = 0; i < r; i++) {
// for(int j = 0; j + 1 < c; j++) cout << h[i][j] << " ";
// cout << endl;
// }
//
// for(int i = 0; i + 1 < r; i++) {
// for(int j = 0; j < c; j++) cout << v[i][j] << " ";
// cout << endl;
// }
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
up(1, 0, r - 1, P);
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
up(1, 0, r - 1, P);
}
int escape(int V1, int V2) {
return T[1][V1][V2];
}
#ifdef ngu
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
static int H[5000][200];
static int V[5000][200];
int main() {
ofstream cout("task.out");
int R, C, E, P, Q, W, V1, V2, event, i, j;
int res;
FILE *f = fopen("task.inp", "r");
if (!f)
fail("Failed to open input file.");
res = fscanf(f, "%d%d", &R, &C);
for (i = 0; i < R; ++i)
for (j = 0; j < C-1; ++j)
res = fscanf(f, "%d", &H[i][j]);
for (i = 0; i < R-1; ++i)
for (j = 0; j < C; ++j)
res = fscanf(f, "%d", &V[i][j]);
init(R, C, H, V);
res = fscanf(f, "%d", &E);
for (i = 0; i < E; i++) {
res = fscanf(f, "%d", &event);
if (event == 1) {
res = fscanf(f, "%d%d%d", &P, &Q, &W);
changeH(P, Q, W);
} else if (event == 2) {
res = fscanf(f, "%d%d%d", &P, &Q, &W);
changeV(P, Q, W);
} else if (event == 3) {
res = fscanf(f, "%d%d", &V1, &V2);
printf("%d\n", escape(V1, V2));
} else
fail("Invalid event type.");
}
fclose(f);
return 0;
cout.close();
}
#endif // ngu
Compilation message
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
15 | int res;
| ^~~
wombats.cpp: In function 'void up(int, int, int, int)':
wombats.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
58192 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
59996 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 5 |
Correct |
3 ms |
16728 KB |
Output is correct |
| 6 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 7 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 8 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 9 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 10 |
Incorrect |
3 ms |
16732 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1755 ms |
42464 KB |
Output is correct |
| 2 |
Correct |
1452 ms |
42412 KB |
Output is correct |
| 3 |
Correct |
1706 ms |
42460 KB |
Output is correct |
| 4 |
Correct |
1824 ms |
42656 KB |
Output is correct |
| 5 |
Incorrect |
1689 ms |
42408 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
62040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1712 ms |
42452 KB |
Output is correct |
| 2 |
Correct |
1478 ms |
42620 KB |
Output is correct |
| 3 |
Correct |
1767 ms |
42456 KB |
Output is correct |
| 4 |
Correct |
1777 ms |
42408 KB |
Output is correct |
| 5 |
Incorrect |
1691 ms |
42404 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1704 ms |
42456 KB |
Output is correct |
| 2 |
Correct |
1493 ms |
42408 KB |
Output is correct |
| 3 |
Correct |
1805 ms |
42324 KB |
Output is correct |
| 4 |
Correct |
1818 ms |
42452 KB |
Output is correct |
| 5 |
Incorrect |
1718 ms |
42412 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
