#include "wombats.h"
#include <cstring>
#include <cstdio>
constexpr int maxm = 205, maxn = 5010, inf = 0x3f3f3f3f, SZ = 11;
struct Node
{
int dp[maxm][maxm];
Node() { memset(dp, 0, sizeof dp); }
};
int min(int a, int b) { return a < b ? a : b; }
int H[maxn][maxm], V[maxn][maxm];
int N, m, qtd_blocks;
void calc(int linha, Node& ans) {
static int dp[SZ+1][maxm];
int tam = min(SZ, N - linha);
for(int coluna = 0; coluna < m; coluna++) {
memset(dp, 0x3f, sizeof dp);
dp[0][coluna] = 0;
for(int i = 0; i < tam; i++) {
for(int j = 1; j < m; j++)
dp[i][j] = min(dp[i][j], dp[i][j-1] + H[i + linha][j-1]);
for(int j = m-2; j >= 0; j--)
dp[i][j] = min(dp[i][j], dp[i][j+1] + H[i + linha][j]);
if(i < tam-1)
for(int j = 0; j < m; j++)
dp[i+1][j] = dp[i][j] + V[i + linha][j];
}
for(int i = 0; i < m; i++)
ans.dp[coluna][i] = dp[tam-1][i];
}
}
void merge(Node L, Node R, Node& ans) {
auto get = [&](int INI, int FIM, int l, int r) {
int ans = inf, opt = l;
for(int i = l; i <= r; i++) {
if(L.dp[INI][i] + R.dp[i][FIM] < ans)
ans = L.dp[INI][i] + R.dp[i][FIM], opt = i;
}
return opt;
};
for(int inicio = 0; inicio < m; inicio++)
for(int i = 0, j = m-1-inicio; j < m; i++, j++)
ans.dp[i][j] = get(i, j, i ? ans.dp[i-1][j] : 0, j<m-1 ? ans.dp[i][j+1] : m-1);
for(int inicio = 1; inicio < m; inicio++)
for(int i = inicio, j = 0; i < m; i++, j++)
ans.dp[i][j] = get(i, j, i ? ans.dp[i-1][j] : 0, j<m-1 ? ans.dp[i][j+1] : m-1);
for(int i = 0; i < m; i++)
for(int j = 0; j < m; j++)
ans.dp[i][j] = L.dp[i][ans.dp[i][j]] + R.dp[ans.dp[i][j]][j];
}
struct SegmentTree
{
Node tree[1<<10];
void build(int node, int i, int j) {
if(i == j) return (void)(calc(i*(SZ-1), tree[node]));
int m = (i+j) >> 1;
build(node<<1, i, m); build(node<<1|1, m+1, j);
merge(tree[node<<1], tree[node<<1|1], tree[node]);
}
int query(int l, int r) { return tree[1].dp[l][r]; }
void upd(int node, int i, int j, int pos) {
if(i == j) return (void)(calc(i*(SZ-1), tree[node]));
int m = (i+j) >> 1;
if(pos <= m) upd(node<<1, i, m, pos);
else upd(node<<1|1, m+1, j, pos);
merge(tree[node<<1], tree[node<<1|1], tree[node]);
}
} seg;
void init(int R, int C, int hor[5000][200], int ver[5000][200]) {
m = C; N = R;
for(int i = 0; i < N; i++)
for(int j = 0; j < m-1; j++)
H[i][j] = hor[i][j];
for(int i = 0; i < N-1; i++)
for(int j = 0; j < m; j++)
V[i][j] = ver[i][j];
qtd_blocks = (N-1) / (SZ-1);
seg.build(1, 0, qtd_blocks);
}
void changeH(int P, int Q, int W) {
H[P][Q] = W;
seg.upd(1, 0, qtd_blocks, P / (SZ-1));
if(P % (SZ-1) == 0 && P)
seg.upd(1, 0, qtd_blocks, P / (SZ-1) - 1);
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
seg.upd(1, 0, qtd_blocks, P / (SZ-1));
}
int escape(int V1, int V2) {
return seg.query(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]
15 | int res;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
207 ms |
176964 KB |
Output is correct |
2 |
Correct |
221 ms |
176960 KB |
Output is correct |
3 |
Correct |
288 ms |
178620 KB |
Output is correct |
4 |
Correct |
210 ms |
176892 KB |
Output is correct |
5 |
Correct |
196 ms |
176956 KB |
Output is correct |
6 |
Correct |
78 ms |
168696 KB |
Output is correct |
7 |
Correct |
77 ms |
168644 KB |
Output is correct |
8 |
Correct |
78 ms |
168644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
168612 KB |
Output is correct |
2 |
Correct |
82 ms |
168832 KB |
Output is correct |
3 |
Correct |
79 ms |
168684 KB |
Output is correct |
4 |
Correct |
78 ms |
169028 KB |
Output is correct |
5 |
Correct |
90 ms |
169016 KB |
Output is correct |
6 |
Correct |
79 ms |
169028 KB |
Output is correct |
7 |
Correct |
78 ms |
169052 KB |
Output is correct |
8 |
Correct |
78 ms |
168988 KB |
Output is correct |
9 |
Correct |
79 ms |
169000 KB |
Output is correct |
10 |
Correct |
80 ms |
169028 KB |
Output is correct |
11 |
Correct |
192 ms |
170036 KB |
Output is correct |
12 |
Correct |
78 ms |
169020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
229 ms |
169284 KB |
Output is correct |
2 |
Correct |
228 ms |
169388 KB |
Output is correct |
3 |
Correct |
248 ms |
169412 KB |
Output is correct |
4 |
Correct |
252 ms |
169364 KB |
Output is correct |
5 |
Correct |
263 ms |
169252 KB |
Output is correct |
6 |
Correct |
79 ms |
168660 KB |
Output is correct |
7 |
Correct |
80 ms |
168772 KB |
Output is correct |
8 |
Correct |
83 ms |
168660 KB |
Output is correct |
9 |
Correct |
827 ms |
169364 KB |
Output is correct |
10 |
Correct |
77 ms |
168644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
208 ms |
184880 KB |
Output is correct |
2 |
Correct |
205 ms |
184936 KB |
Output is correct |
3 |
Correct |
230 ms |
184780 KB |
Output is correct |
4 |
Correct |
253 ms |
185588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
232 ms |
169328 KB |
Output is correct |
2 |
Correct |
226 ms |
169356 KB |
Output is correct |
3 |
Correct |
251 ms |
169284 KB |
Output is correct |
4 |
Correct |
248 ms |
169444 KB |
Output is correct |
5 |
Correct |
240 ms |
169364 KB |
Output is correct |
6 |
Correct |
213 ms |
184884 KB |
Output is correct |
7 |
Correct |
223 ms |
184956 KB |
Output is correct |
8 |
Correct |
222 ms |
184884 KB |
Output is correct |
9 |
Correct |
253 ms |
185600 KB |
Output is correct |
10 |
Correct |
211 ms |
176952 KB |
Output is correct |
11 |
Correct |
202 ms |
177040 KB |
Output is correct |
12 |
Correct |
295 ms |
178464 KB |
Output is correct |
13 |
Correct |
218 ms |
177068 KB |
Output is correct |
14 |
Correct |
198 ms |
176960 KB |
Output is correct |
15 |
Correct |
76 ms |
168692 KB |
Output is correct |
16 |
Correct |
83 ms |
168668 KB |
Output is correct |
17 |
Correct |
92 ms |
168680 KB |
Output is correct |
18 |
Correct |
77 ms |
169084 KB |
Output is correct |
19 |
Correct |
79 ms |
169084 KB |
Output is correct |
20 |
Correct |
78 ms |
168992 KB |
Output is correct |
21 |
Correct |
79 ms |
169016 KB |
Output is correct |
22 |
Correct |
80 ms |
169012 KB |
Output is correct |
23 |
Correct |
80 ms |
168988 KB |
Output is correct |
24 |
Correct |
77 ms |
169028 KB |
Output is correct |
25 |
Correct |
159 ms |
170024 KB |
Output is correct |
26 |
Correct |
81 ms |
169008 KB |
Output is correct |
27 |
Correct |
831 ms |
169372 KB |
Output is correct |
28 |
Correct |
1834 ms |
185220 KB |
Output is correct |
29 |
Correct |
1801 ms |
182420 KB |
Output is correct |
30 |
Correct |
1788 ms |
182344 KB |
Output is correct |
31 |
Correct |
1880 ms |
186312 KB |
Output is correct |
32 |
Correct |
79 ms |
168612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
236 ms |
169356 KB |
Output is correct |
2 |
Correct |
227 ms |
169356 KB |
Output is correct |
3 |
Correct |
247 ms |
169312 KB |
Output is correct |
4 |
Correct |
242 ms |
169368 KB |
Output is correct |
5 |
Correct |
248 ms |
169336 KB |
Output is correct |
6 |
Correct |
209 ms |
184876 KB |
Output is correct |
7 |
Correct |
211 ms |
184936 KB |
Output is correct |
8 |
Correct |
228 ms |
184920 KB |
Output is correct |
9 |
Correct |
252 ms |
185576 KB |
Output is correct |
10 |
Correct |
206 ms |
176964 KB |
Output is correct |
11 |
Correct |
202 ms |
176944 KB |
Output is correct |
12 |
Correct |
281 ms |
178500 KB |
Output is correct |
13 |
Correct |
222 ms |
176920 KB |
Output is correct |
14 |
Correct |
208 ms |
176884 KB |
Output is correct |
15 |
Correct |
2512 ms |
184940 KB |
Output is correct |
16 |
Correct |
6622 ms |
186412 KB |
Output is correct |
17 |
Correct |
79 ms |
168644 KB |
Output is correct |
18 |
Correct |
80 ms |
168680 KB |
Output is correct |
19 |
Correct |
81 ms |
168704 KB |
Output is correct |
20 |
Correct |
78 ms |
169060 KB |
Output is correct |
21 |
Correct |
78 ms |
169028 KB |
Output is correct |
22 |
Correct |
89 ms |
169064 KB |
Output is correct |
23 |
Correct |
93 ms |
169080 KB |
Output is correct |
24 |
Correct |
80 ms |
169028 KB |
Output is correct |
25 |
Correct |
79 ms |
169092 KB |
Output is correct |
26 |
Correct |
81 ms |
169040 KB |
Output is correct |
27 |
Correct |
162 ms |
170104 KB |
Output is correct |
28 |
Correct |
79 ms |
168992 KB |
Output is correct |
29 |
Correct |
830 ms |
169372 KB |
Output is correct |
30 |
Correct |
1866 ms |
185296 KB |
Output is correct |
31 |
Correct |
6313 ms |
185772 KB |
Output is correct |
32 |
Correct |
6235 ms |
185576 KB |
Output is correct |
33 |
Correct |
1767 ms |
182320 KB |
Output is correct |
34 |
Correct |
6273 ms |
182812 KB |
Output is correct |
35 |
Correct |
1785 ms |
182412 KB |
Output is correct |
36 |
Correct |
6205 ms |
182732 KB |
Output is correct |
37 |
Correct |
1881 ms |
186236 KB |
Output is correct |
38 |
Correct |
6267 ms |
186248 KB |
Output is correct |
39 |
Correct |
77 ms |
168644 KB |
Output is correct |
40 |
Correct |
6288 ms |
182720 KB |
Output is correct |