#pragma GCC optimize("O3")
#pragma GCC target("arch=haswell")
#include <bits/stdc++.h>
#include "wombats.h"
#define rep(i,n) for(int i=0; i<n; i++)
#define reset(a) memset(a, 0x3f, sizeof a)
using namespace std;
constexpr int K=20, SZ=512;
int N, M, X[5000][200], Y[5000][200];
int T[SZ][200][200], L[SZ], R[SZ], id=1;
int& mini(int& x, int y) { return x=min(x, y); }
void build(int l, int r, int s=0, int e=N-1, int t=0) {
auto &D=T[t];
reset(D);
if(s==e) {
rep(i, M) D[i][i]=0;
rep(y, K) {
int i=s*K+y;
rep(j, M) {
rep(k, M-1) mini(D[j][k+1], D[j][k]+X[i][k]);
rep(k, M-1) mini(D[j][M-k-2], D[j][M-k-1]+X[i][M-k-2]);
rep(k, M) D[j][k]+=Y[i][k];
}
}
return;
}
int m=s+e>>1;
if(l<=m) build(l, r, s, m, L[t]=L[t] ?: id++);
if(r>m) build(l, r, m+1, e, R[t]=R[t] ?: id++);
auto &A=T[L[t]], &B=T[R[t]];
rep(a, M) rep(i, M) rep(b, M)
D[a][b]=min(D[a][b], A[a][i]+B[i][b]);
}
void init(int P, int Q, int H[5000][200], int V[5000][200]) {
N=(P+K-1)/K, M=Q;
reset(X);
rep(i, P) rep(j, Q-1) X[i][j]=H[i][j];
rep(i, P-1) rep(j, Q) Y[i][j]=V[i][j];
build(0, N-1);
}
void changeH(int p, int q, int w) { X[p][q]=w; build(p/K, p/K); }
void changeV(int p, int q, int w) { Y[p][q]=w; build(p/K, p/K); }
int escape(int a, int b) { return T[0][a][b]; }
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;
^~~
wombats.cpp: In function 'void build(int, int, int, int, int)':
wombats.cpp:29:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=s+e>>1;
~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
85 ms |
90360 KB |
Output is correct |
2 |
Correct |
82 ms |
90232 KB |
Output is correct |
3 |
Correct |
162 ms |
91860 KB |
Output is correct |
4 |
Correct |
96 ms |
90248 KB |
Output is correct |
5 |
Correct |
84 ms |
90360 KB |
Output is correct |
6 |
Correct |
7 ms |
4480 KB |
Output is correct |
7 |
Correct |
7 ms |
4352 KB |
Output is correct |
8 |
Correct |
7 ms |
4352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
4480 KB |
Output is correct |
2 |
Correct |
7 ms |
4352 KB |
Output is correct |
3 |
Correct |
6 ms |
4352 KB |
Output is correct |
4 |
Correct |
7 ms |
4480 KB |
Output is correct |
5 |
Correct |
7 ms |
4480 KB |
Output is correct |
6 |
Correct |
7 ms |
4480 KB |
Output is correct |
7 |
Correct |
7 ms |
4480 KB |
Output is correct |
8 |
Correct |
7 ms |
4480 KB |
Output is correct |
9 |
Correct |
7 ms |
4480 KB |
Output is correct |
10 |
Correct |
7 ms |
4480 KB |
Output is correct |
11 |
Correct |
93 ms |
6904 KB |
Output is correct |
12 |
Correct |
7 ms |
4480 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
131 ms |
5888 KB |
Output is correct |
2 |
Correct |
151 ms |
6136 KB |
Output is correct |
3 |
Correct |
147 ms |
6016 KB |
Output is correct |
4 |
Correct |
135 ms |
6036 KB |
Output is correct |
5 |
Correct |
142 ms |
6016 KB |
Output is correct |
6 |
Correct |
7 ms |
4352 KB |
Output is correct |
7 |
Correct |
7 ms |
4352 KB |
Output is correct |
8 |
Correct |
6 ms |
4352 KB |
Output is correct |
9 |
Correct |
716 ms |
6112 KB |
Output is correct |
10 |
Correct |
8 ms |
4480 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
83 ms |
94072 KB |
Output is correct |
2 |
Correct |
85 ms |
94072 KB |
Output is correct |
3 |
Correct |
101 ms |
94136 KB |
Output is correct |
4 |
Correct |
125 ms |
94840 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
130 ms |
5888 KB |
Output is correct |
2 |
Correct |
145 ms |
6016 KB |
Output is correct |
3 |
Correct |
141 ms |
6136 KB |
Output is correct |
4 |
Correct |
134 ms |
6016 KB |
Output is correct |
5 |
Correct |
144 ms |
6264 KB |
Output is correct |
6 |
Correct |
81 ms |
94204 KB |
Output is correct |
7 |
Correct |
84 ms |
94200 KB |
Output is correct |
8 |
Correct |
99 ms |
94200 KB |
Output is correct |
9 |
Correct |
127 ms |
95608 KB |
Output is correct |
10 |
Correct |
79 ms |
90232 KB |
Output is correct |
11 |
Correct |
80 ms |
90232 KB |
Output is correct |
12 |
Correct |
164 ms |
93048 KB |
Output is correct |
13 |
Correct |
94 ms |
90280 KB |
Output is correct |
14 |
Correct |
81 ms |
90232 KB |
Output is correct |
15 |
Correct |
7 ms |
4480 KB |
Output is correct |
16 |
Correct |
6 ms |
4352 KB |
Output is correct |
17 |
Correct |
7 ms |
4352 KB |
Output is correct |
18 |
Correct |
7 ms |
4480 KB |
Output is correct |
19 |
Correct |
7 ms |
4480 KB |
Output is correct |
20 |
Correct |
7 ms |
4480 KB |
Output is correct |
21 |
Correct |
7 ms |
4480 KB |
Output is correct |
22 |
Correct |
7 ms |
4480 KB |
Output is correct |
23 |
Correct |
7 ms |
4480 KB |
Output is correct |
24 |
Correct |
7 ms |
4480 KB |
Output is correct |
25 |
Correct |
92 ms |
6904 KB |
Output is correct |
26 |
Correct |
7 ms |
4480 KB |
Output is correct |
27 |
Correct |
693 ms |
6136 KB |
Output is correct |
28 |
Correct |
1717 ms |
98432 KB |
Output is correct |
29 |
Correct |
1632 ms |
81912 KB |
Output is correct |
30 |
Correct |
1650 ms |
82040 KB |
Output is correct |
31 |
Correct |
1759 ms |
100088 KB |
Output is correct |
32 |
Correct |
7 ms |
4480 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
129 ms |
5888 KB |
Output is correct |
2 |
Correct |
147 ms |
6016 KB |
Output is correct |
3 |
Correct |
142 ms |
6044 KB |
Output is correct |
4 |
Correct |
140 ms |
6136 KB |
Output is correct |
5 |
Correct |
148 ms |
6016 KB |
Output is correct |
6 |
Correct |
82 ms |
94200 KB |
Output is correct |
7 |
Correct |
81 ms |
94200 KB |
Output is correct |
8 |
Correct |
98 ms |
94200 KB |
Output is correct |
9 |
Correct |
127 ms |
95608 KB |
Output is correct |
10 |
Correct |
78 ms |
90232 KB |
Output is correct |
11 |
Correct |
78 ms |
90240 KB |
Output is correct |
12 |
Correct |
162 ms |
93048 KB |
Output is correct |
13 |
Correct |
95 ms |
90232 KB |
Output is correct |
14 |
Correct |
79 ms |
90232 KB |
Output is correct |
15 |
Correct |
1311 ms |
103928 KB |
Output is correct |
16 |
Correct |
7737 ms |
105308 KB |
Output is correct |
17 |
Correct |
7 ms |
4352 KB |
Output is correct |
18 |
Correct |
6 ms |
4352 KB |
Output is correct |
19 |
Correct |
6 ms |
4352 KB |
Output is correct |
20 |
Correct |
7 ms |
4436 KB |
Output is correct |
21 |
Correct |
7 ms |
4480 KB |
Output is correct |
22 |
Correct |
7 ms |
4480 KB |
Output is correct |
23 |
Correct |
7 ms |
4480 KB |
Output is correct |
24 |
Correct |
7 ms |
4480 KB |
Output is correct |
25 |
Correct |
7 ms |
4480 KB |
Output is correct |
26 |
Correct |
7 ms |
4480 KB |
Output is correct |
27 |
Correct |
92 ms |
6904 KB |
Output is correct |
28 |
Correct |
7 ms |
4480 KB |
Output is correct |
29 |
Correct |
700 ms |
6136 KB |
Output is correct |
30 |
Correct |
1717 ms |
98552 KB |
Output is correct |
31 |
Correct |
7576 ms |
102676 KB |
Output is correct |
32 |
Correct |
7583 ms |
102704 KB |
Output is correct |
33 |
Correct |
1655 ms |
82168 KB |
Output is correct |
34 |
Correct |
7279 ms |
85948 KB |
Output is correct |
35 |
Correct |
1620 ms |
81784 KB |
Output is correct |
36 |
Correct |
7249 ms |
86084 KB |
Output is correct |
37 |
Correct |
1807 ms |
100280 KB |
Output is correct |
38 |
Correct |
7589 ms |
103316 KB |
Output is correct |
39 |
Correct |
6 ms |
4480 KB |
Output is correct |
40 |
Correct |
7273 ms |
86240 KB |
Output is correct |