#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
struct matrix {
int a[202][202];
};
const int lim = 5004;
int r, c, h[5004][204], v[5004][204], hs[5004][204], thr[204][204];
bool f[20004];
matrix m[5004], all;
inline int hsum(int k, int x, int y) {
if (x>y) swap(x, y);
return x ? (hs[k][y] - hs[k][x]) : hs[k][y];
}
matrix sum(matrix &a, matrix &b, int k) {
matrix ret;
for (int i=0; i<=c; i++) thr[i][c-i+1] = c-1;
for (int tog=0; tog<2; tog++) for (int j=c-1; j>=0; j--) for (int i=0; i+j<c; i++) {
int mn = 2e9, mp = -1;
int x = tog ? (i+j) : i, y = tog ? i : (i+j);
for (int t=thr[j+1][i]; t<=thr[j+1][i+1]; t++) {
int now = a.a[x][t] + v[k][t] + b.a[t][y];
if (now <= mn) mn = now, mp = t;
}
if (tog) ret.a[i+j][i] = mn;
else ret.a[i][i+j] = mn;
thr[j][i+1] = mp;
}
return ret;
}
matrix base(int k) {
matrix ret;
for (int i=0; i<c; i++) for (int j=0; j<c; j++) ret.a[i][j] = hsum(k, i, j);
return ret;
}
matrix get(int s, int e, int x, int all) {
if (s==e) return base(s);
if (!all and x<lim and f[x]) return m[x];
int mid = (s+e)/2;
f[x] = 1;
matrix l = get(s, mid, 2*x, all), r = get(mid+1, e, 2*x+1, all);
return m[x] = sum(l, r, mid);
}
matrix update(int s, int e, int x, int p) {
if (s==e) return get(s, e, x, 0);
int k = (s+e)/2;
if (p<=k) update(s, k, 2*x, p);
else update(k+1, e, 2*x+1, p);
if (x<lim) f[x] = 0;
return get(s, e, x, 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<c-1; j++) h[i][j] = H[i][j], hs[i][j+1] = hs[i][j] + h[i][j];
for (int i=0; i<r-1; i++) for (int j=0; j<c; j++) v[i][j] = V[i][j];
all = get(0, r-1, 1, 1);
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
for (int j=0; j<c-1; j++) hs[P][j+1] = hs[P][j] + h[P][j];
all = update(0, r-1, 1, P);
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
all = update(0, r-1, 1, P);
}
int escape(int V1, int V2) {
return all.a[V1][V2];
}
Compilation message
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
