#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr \
if (false) \
cerr
#endif
#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())
#ifdef __cplusplus
extern "C" {
#endif
void init(int R, int C, int H[5000][200], int V[5000][200]);
void changeH(int P, int Q, int W);
void changeV(int P, int Q, int W);
int escape(int V1, int V2);
#ifdef __cplusplus
}
#endif
const int maxn = 5005, maxm = 105;
template <int N, int M>
using mat = array<array<int, M>, N>;
template <int A, int B, int C>
mat<A, C> mul(const mat<A, B>& x, const mat<B, C>& y) {
mat<A, C> ans;
for (auto& a : ans) {
a.fill(1e9);
}
for (int i = 0; i < A; i++) {
for (int j = 0; j < B; j++) {
for (int k = 0; k < C; k++) {
ans[i][k] = min(ans[i][k], x[i][j] + y[j][k]);
}
}
}
return ans;
}
int n, m, t, last_upd, harr[5000][200], varr[5000][200];
mat<maxm, maxm> ans;
mat<maxm, maxm> solve(int l, int r) {
mat<maxm, maxm> ans {};
for (int i = 0; i < m; i++) {
auto& dp = ans[i];
dp.fill(1e9);
dp[i] = 0;
for (int j = l; j < r; j++) {
array<int, maxm> ndp;
ndp.fill(1e9);
int psum[m + 1];
psum[0] = 0;
partial_sum(harr[j], harr[j] + m, psum + 1);
int ans = 1e9;
for (int k = 0; k < m; k++) {
ans = min(ans, dp[k] - psum[k]);
if (!i && j == n - 1) {
dbg(k, ans, varr[j][k], psum[k]);
}
ndp[k] = min(ndp[k], ans + varr[j][k] + psum[k]);
}
ans = 1e9;
for (int k = m - 1; k >= 0; k--) {
ans = min(ans, dp[k] + psum[k]);
ndp[k] = min(ndp[k], ans + varr[j][k] - psum[k]);
}
swap(dp, ndp);
}
}
return ans;
}
void init(int _n, int _m, int _harr[5000][200], int _varr[5000][200]) {
n = _n;
m = _m;
memcpy(harr, _harr, sizeof(harr));
memcpy(varr, _varr, sizeof(varr));
last_upd = -1;
}
void changeH(int x, int y, int w) {
t++;
harr[x][y] = w;
}
void changeV(int x, int y, int w) {
t++;
varr[x][y] = w;
}
int escape(int a, int b) {
if (last_upd < t) {
ans = solve(0, n);
last_upd = t;
}
return ans[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]
15 | int res;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
338 ms |
12136 KB |
Output is correct |
2 |
Correct |
377 ms |
12116 KB |
Output is correct |
3 |
Correct |
416 ms |
14912 KB |
Output is correct |
4 |
Correct |
359 ms |
12236 KB |
Output is correct |
5 |
Correct |
368 ms |
12144 KB |
Output is correct |
6 |
Correct |
5 ms |
8112 KB |
Output is correct |
7 |
Correct |
5 ms |
8148 KB |
Output is correct |
8 |
Correct |
5 ms |
8148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
8120 KB |
Output is correct |
2 |
Correct |
6 ms |
8148 KB |
Output is correct |
3 |
Correct |
6 ms |
8148 KB |
Output is correct |
4 |
Correct |
5 ms |
8148 KB |
Output is correct |
5 |
Correct |
5 ms |
8148 KB |
Output is correct |
6 |
Correct |
5 ms |
8148 KB |
Output is correct |
7 |
Correct |
6 ms |
8244 KB |
Output is correct |
8 |
Correct |
5 ms |
8148 KB |
Output is correct |
9 |
Correct |
5 ms |
8148 KB |
Output is correct |
10 |
Correct |
4 ms |
8148 KB |
Output is correct |
11 |
Correct |
71 ms |
10548 KB |
Output is correct |
12 |
Correct |
5 ms |
8148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
48 ms |
8456 KB |
Output is correct |
2 |
Correct |
290 ms |
8440 KB |
Output is correct |
3 |
Correct |
349 ms |
8404 KB |
Output is correct |
4 |
Correct |
353 ms |
8452 KB |
Output is correct |
5 |
Correct |
359 ms |
8452 KB |
Output is correct |
6 |
Correct |
6 ms |
8108 KB |
Output is correct |
7 |
Correct |
4 ms |
8276 KB |
Output is correct |
8 |
Correct |
4 ms |
8116 KB |
Output is correct |
9 |
Correct |
129 ms |
8448 KB |
Output is correct |
10 |
Correct |
4 ms |
8148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
687 ms |
16096 KB |
Output is correct |
2 |
Correct |
683 ms |
16084 KB |
Output is correct |
3 |
Correct |
695 ms |
16092 KB |
Output is correct |
4 |
Correct |
718 ms |
17448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
8404 KB |
Output is correct |
2 |
Correct |
330 ms |
8436 KB |
Output is correct |
3 |
Correct |
323 ms |
8456 KB |
Output is correct |
4 |
Correct |
349 ms |
8456 KB |
Output is correct |
5 |
Correct |
324 ms |
8404 KB |
Output is correct |
6 |
Correct |
673 ms |
16096 KB |
Output is correct |
7 |
Correct |
728 ms |
16084 KB |
Output is correct |
8 |
Correct |
671 ms |
16088 KB |
Output is correct |
9 |
Correct |
771 ms |
17448 KB |
Output is correct |
10 |
Correct |
344 ms |
12136 KB |
Output is correct |
11 |
Correct |
341 ms |
12144 KB |
Output is correct |
12 |
Correct |
416 ms |
14868 KB |
Output is correct |
13 |
Correct |
340 ms |
12116 KB |
Output is correct |
14 |
Correct |
370 ms |
12140 KB |
Output is correct |
15 |
Correct |
5 ms |
8148 KB |
Output is correct |
16 |
Correct |
4 ms |
8148 KB |
Output is correct |
17 |
Correct |
5 ms |
8148 KB |
Output is correct |
18 |
Correct |
5 ms |
8148 KB |
Output is correct |
19 |
Correct |
5 ms |
8276 KB |
Output is correct |
20 |
Correct |
4 ms |
8148 KB |
Output is correct |
21 |
Correct |
4 ms |
8148 KB |
Output is correct |
22 |
Correct |
5 ms |
8148 KB |
Output is correct |
23 |
Correct |
6 ms |
8148 KB |
Output is correct |
24 |
Correct |
4 ms |
8148 KB |
Output is correct |
25 |
Correct |
95 ms |
10596 KB |
Output is correct |
26 |
Correct |
4 ms |
8276 KB |
Output is correct |
27 |
Correct |
131 ms |
8444 KB |
Output is correct |
28 |
Execution timed out |
20056 ms |
19880 KB |
Time limit exceeded |
29 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
8420 KB |
Output is correct |
2 |
Correct |
296 ms |
8444 KB |
Output is correct |
3 |
Correct |
313 ms |
8452 KB |
Output is correct |
4 |
Correct |
340 ms |
8464 KB |
Output is correct |
5 |
Correct |
320 ms |
8456 KB |
Output is correct |
6 |
Correct |
679 ms |
16096 KB |
Output is correct |
7 |
Correct |
698 ms |
16084 KB |
Output is correct |
8 |
Correct |
689 ms |
16092 KB |
Output is correct |
9 |
Correct |
706 ms |
17556 KB |
Output is correct |
10 |
Correct |
349 ms |
12132 KB |
Output is correct |
11 |
Correct |
332 ms |
12148 KB |
Output is correct |
12 |
Correct |
424 ms |
14820 KB |
Output is correct |
13 |
Correct |
334 ms |
12096 KB |
Output is correct |
14 |
Correct |
335 ms |
12156 KB |
Output is correct |
15 |
Runtime error |
645 ms |
42024 KB |
Execution killed with signal 11 |
16 |
Halted |
0 ms |
0 KB |
- |