oj.uz

Submission #605680

# Submission time Handle Problem Language Result Execution time Memory
605680 2022-07-25T22:22:36 Z skittles1412 Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 42024 KB 
#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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory 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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory 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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory 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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory 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

Subtask #5
0 / 21.0

# Verdict Execution time Memory 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 -

Subtask #6
0 / 24.0

# Verdict Execution time Memory 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 -