#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<int> > Paths;
const int MAXD = 100000000; // 1e8
int r;
int c;
vector<vector<int> > h;
vector<vector<int> > v;
void pr(const Paths &ans){
for(int i = 0; i < c; i++){
for(int j = 0; j < c; j++){
cout << ans[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void dnc(const Paths &a, const Paths &b, Paths &paths, int t, int bl, int br, int ml, int mr){
if(bl > br) return;
// top, bottom left, bottom right
int bm = (bl + br) / 2;
int best = MAXD + 1;
int bestm = -1;
for(int m = ml; m <= mr; m++){
int dist = a[t][m] + b[m][bm];
if(dist < best){
best = dist;
bestm = m;
}
}
assert(bestm != -1);
paths[t][bm] = best;
dnc(a, b, paths, t, bl, bm - 1, ml, bestm);
dnc(a, b, paths, t, bm + 1, br, bestm, mr);
}
Paths join(const Paths &a, const Paths &b){
Paths paths(c, vector<int>(c, MAXD));
for(int i = 0; i < c; i++){
dnc(a, b, paths, i, 0, c-1, 0, c-1);
}
return paths;
}
Paths horizontal(int row){
vector<int> psums(c);
psums[0] = 0;
for(int i = 1; i < c; i++){
psums[i] = psums[i-1] + h[row][i-1];
}
Paths paths(c, vector<int>(c, MAXD));
for(int i = 0; i < c; i++){
for(int j = 0; j < c; j++){
paths[i][j] = abs(psums[j] - psums[i]) + v[row][j];
}
}
return paths;
}
Paths make_interval(int r1, int r2){
Paths p(c, vector<int>(c, MAXD));
// r1 -> r2
for(int st = 0; st < c; st++){
vector<int> dist(c, MAXD);
dist[st] = 0;
for(int row = r1; row <= r2; row++){
for(int i = 0; i + 1 < c; i++){
dist[i+1] = min(dist[i+1], dist[i] + h[row][i]);
}
for(int i = c - 1; i > 0; i--){
dist[i-1] = min(dist[i-1], dist[i] + h[row][i-1]);
}
for(int i = 0; i < c; i++){
dist[i] += v[row][i];
}
}
for(int i = 0; i < c; i++){
p[st][i] = dist[i];
}
}
return p;
}
Paths ans;
struct node {
Paths p;
node *l, *r;
int lx, rx;
};
const int BLOCKSZ = 15;
node* build(int lx, int rx){
node* v = new node();
v->lx = lx;
v->rx = rx;
if(rx - lx + 1 <= BLOCKSZ){
v->l = v->r = NULL;
v->p = make_interval(v->lx, v->rx);
} else {
int mx = (lx + rx) / 2;
v->l = build(lx, mx);
v->r = build(mx + 1, rx);
v->p = join(v->l->p, v->r->p);
}
return v;
}
void upd(node* v, int x, int y){
if(y < v->lx || x > v->rx) return;
if(v->l == NULL && v->r == NULL){
v->p = make_interval(v->lx, v->rx);
} else {
upd(v->l, x, y);
upd(v->r, x, y);
v->p = join(v->l->p, v->r->p);
}
}
node* tree;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
r = R;
c = C;
h.resize(r, vector<int>(c-1, 0));
v.resize(r, vector<int>(c, 0));
for(int i = 0; i < r; i++){
for(int j = 0; j < c-1; j++){
h[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];
}
}
tree = build(0, r-1);
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
upd(tree, P-1, P);
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
upd(tree, P, P);
}
int escape(int V1, int V2) {
return tree->p[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;
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
4784 KB |
Output is correct |
2 |
Correct |
10 ms |
4784 KB |
Output is correct |
3 |
Correct |
87 ms |
6536 KB |
Output is correct |
4 |
Correct |
10 ms |
6536 KB |
Output is correct |
5 |
Correct |
9 ms |
6536 KB |
Output is correct |
6 |
Correct |
3 ms |
6536 KB |
Output is correct |
7 |
Correct |
3 ms |
6536 KB |
Output is correct |
8 |
Correct |
3 ms |
6536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
6536 KB |
Output is correct |
2 |
Correct |
2 ms |
6536 KB |
Output is correct |
3 |
Correct |
2 ms |
6536 KB |
Output is correct |
4 |
Correct |
3 ms |
6536 KB |
Output is correct |
5 |
Correct |
3 ms |
6536 KB |
Output is correct |
6 |
Correct |
3 ms |
6536 KB |
Output is correct |
7 |
Correct |
3 ms |
6536 KB |
Output is correct |
8 |
Correct |
3 ms |
6536 KB |
Output is correct |
9 |
Correct |
3 ms |
6536 KB |
Output is correct |
10 |
Correct |
3 ms |
6536 KB |
Output is correct |
11 |
Correct |
100 ms |
6536 KB |
Output is correct |
12 |
Correct |
3 ms |
6536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
160 ms |
6536 KB |
Output is correct |
2 |
Correct |
153 ms |
6536 KB |
Output is correct |
3 |
Correct |
156 ms |
6536 KB |
Output is correct |
4 |
Correct |
195 ms |
6536 KB |
Output is correct |
5 |
Correct |
179 ms |
6536 KB |
Output is correct |
6 |
Correct |
2 ms |
6536 KB |
Output is correct |
7 |
Correct |
2 ms |
6536 KB |
Output is correct |
8 |
Correct |
3 ms |
6536 KB |
Output is correct |
9 |
Correct |
641 ms |
6536 KB |
Output is correct |
10 |
Correct |
2 ms |
6536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
9244 KB |
Output is correct |
2 |
Correct |
14 ms |
9244 KB |
Output is correct |
3 |
Correct |
14 ms |
9260 KB |
Output is correct |
4 |
Correct |
55 ms |
9972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
206 ms |
9972 KB |
Output is correct |
2 |
Correct |
138 ms |
9972 KB |
Output is correct |
3 |
Correct |
172 ms |
9972 KB |
Output is correct |
4 |
Correct |
163 ms |
9972 KB |
Output is correct |
5 |
Correct |
144 ms |
9972 KB |
Output is correct |
6 |
Correct |
16 ms |
9972 KB |
Output is correct |
7 |
Correct |
12 ms |
9972 KB |
Output is correct |
8 |
Correct |
13 ms |
9972 KB |
Output is correct |
9 |
Correct |
85 ms |
10024 KB |
Output is correct |
10 |
Correct |
11 ms |
10024 KB |
Output is correct |
11 |
Correct |
10 ms |
10024 KB |
Output is correct |
12 |
Correct |
92 ms |
10024 KB |
Output is correct |
13 |
Correct |
8 ms |
10024 KB |
Output is correct |
14 |
Correct |
7 ms |
10024 KB |
Output is correct |
15 |
Correct |
2 ms |
10024 KB |
Output is correct |
16 |
Correct |
2 ms |
10024 KB |
Output is correct |
17 |
Correct |
2 ms |
10024 KB |
Output is correct |
18 |
Correct |
4 ms |
10024 KB |
Output is correct |
19 |
Correct |
2 ms |
10024 KB |
Output is correct |
20 |
Correct |
4 ms |
10024 KB |
Output is correct |
21 |
Correct |
2 ms |
10024 KB |
Output is correct |
22 |
Correct |
2 ms |
10024 KB |
Output is correct |
23 |
Correct |
3 ms |
10024 KB |
Output is correct |
24 |
Correct |
4 ms |
10024 KB |
Output is correct |
25 |
Correct |
110 ms |
10024 KB |
Output is correct |
26 |
Correct |
3 ms |
10024 KB |
Output is correct |
27 |
Correct |
776 ms |
10024 KB |
Output is correct |
28 |
Correct |
2097 ms |
57500 KB |
Output is correct |
29 |
Correct |
2054 ms |
57500 KB |
Output is correct |
30 |
Correct |
2084 ms |
57500 KB |
Output is correct |
31 |
Correct |
2007 ms |
58512 KB |
Output is correct |
32 |
Correct |
4 ms |
58512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
137 ms |
58512 KB |
Output is correct |
2 |
Correct |
142 ms |
58512 KB |
Output is correct |
3 |
Correct |
180 ms |
58512 KB |
Output is correct |
4 |
Correct |
153 ms |
58512 KB |
Output is correct |
5 |
Correct |
147 ms |
58512 KB |
Output is correct |
6 |
Correct |
14 ms |
58512 KB |
Output is correct |
7 |
Correct |
13 ms |
58512 KB |
Output is correct |
8 |
Correct |
15 ms |
58512 KB |
Output is correct |
9 |
Correct |
54 ms |
58512 KB |
Output is correct |
10 |
Correct |
11 ms |
58512 KB |
Output is correct |
11 |
Correct |
9 ms |
58512 KB |
Output is correct |
12 |
Correct |
139 ms |
58512 KB |
Output is correct |
13 |
Correct |
10 ms |
58512 KB |
Output is correct |
14 |
Correct |
9 ms |
58512 KB |
Output is correct |
15 |
Correct |
1750 ms |
185264 KB |
Output is correct |
16 |
Correct |
8048 ms |
186764 KB |
Output is correct |
17 |
Correct |
3 ms |
186764 KB |
Output is correct |
18 |
Correct |
3 ms |
186764 KB |
Output is correct |
19 |
Correct |
2 ms |
186764 KB |
Output is correct |
20 |
Correct |
3 ms |
186764 KB |
Output is correct |
21 |
Correct |
3 ms |
186764 KB |
Output is correct |
22 |
Correct |
2 ms |
186764 KB |
Output is correct |
23 |
Correct |
3 ms |
186764 KB |
Output is correct |
24 |
Correct |
4 ms |
186764 KB |
Output is correct |
25 |
Correct |
3 ms |
186764 KB |
Output is correct |
26 |
Correct |
2 ms |
186764 KB |
Output is correct |
27 |
Correct |
142 ms |
186764 KB |
Output is correct |
28 |
Correct |
3 ms |
186764 KB |
Output is correct |
29 |
Correct |
773 ms |
186764 KB |
Output is correct |
30 |
Correct |
2058 ms |
186764 KB |
Output is correct |
31 |
Correct |
9127 ms |
186764 KB |
Output is correct |
32 |
Correct |
8506 ms |
186764 KB |
Output is correct |
33 |
Correct |
1938 ms |
186764 KB |
Output is correct |
34 |
Correct |
8256 ms |
186764 KB |
Output is correct |
35 |
Correct |
2165 ms |
186764 KB |
Output is correct |
36 |
Correct |
8988 ms |
186764 KB |
Output is correct |
37 |
Correct |
1978 ms |
186764 KB |
Output is correct |
38 |
Correct |
8534 ms |
194240 KB |
Output is correct |
39 |
Correct |
4 ms |
194240 KB |
Output is correct |
40 |
Correct |
8957 ms |
198064 KB |
Output is correct |