oj.uz

Submission #605706

# Submission time Handle Problem Language Result Execution time Memory
605706 2022-07-25T23:23:59 Z skittles1412 Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 30372 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

template <typename T, size_t N>
ostream& operator<<(ostream& out, const array<T, N>& arr) {
    out << "{";
    for (size_t i = 0; i < N; i++) {
        out << arr[i];
        if (i + 1 < N) {
            out << ", ";
        }
    }
    return out << "}";
}

const int maxn = 5005, maxm = 205, bsize = 320, maxt = 16;
// const int maxn = 32, maxm = 10, bsize = 2, maxt = 16;

static_assert((maxn - 1) / bsize < maxt);

template <size_t N, size_t M>
using mat = array<array<int, M>, N>;

template <size_t A, size_t B, size_t 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 (size_t i = 0; i < A; i++) {
        for (size_t j = 0; j < B; j++) {
            for (size_t k = 0; k < C; k++) {
                ans[i][k] = min(ans[i][k], x[i][j] + y[j][k]);
            }
        }
    }
    return ans;
}

int n, m, harr[5000][200], varr[5000][200];
mat<maxm, maxm> v[maxt * 2];

mat<maxm, maxm> solve(int l, int r) {
    mat<maxm, maxm> ans {};
    for (int i = 0; i < maxm; i++) {
        ans[i].fill(1e9);
        ans[i][i] = 0;
    }
    for (int i = 0; i < m; i++) {
        auto& dp = ans[i];
        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]);
                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 update_leaf(int ind) {
    int x = ind - maxt;
    v[ind] = solve(x * bsize, min(n, (x + 1) * bsize));
}

void maintain(int o) {
    v[o] = mul(v[o * 2], v[o * 2 + 1]);
}

void init(int _n, int _m, int _harr[5000][200], int _varr[5000][200]) {
    n = _n;
    m = _m;
    for (int i = 0; i < n; i++) {
        copy(_harr[i], _harr[i] + m, harr[i]);
        copy(_varr[i], _varr[i] + m, varr[i]);
    }
    for (int i = maxt; i < 2 * maxt; i++) {
        update_leaf(i);
    }
    for (int i = maxt - 1; i; i--) {
        maintain(i);
    }
}

void update(int ind) {
    ind /= bsize;
    ind += maxt;
    update_leaf(ind);
    while (true) {
        ind >>= 1;
        if (!ind) {
            break;
        }
        maintain(ind);
    }
}

void changeH(int x, int y, int w) {
    harr[x][y] = w;
    update(x);
}

void changeV(int x, int y, int w) {
    varr[x][y] = w;
    update(x);
}

int escape(int a, int b) {
    return v[1][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 15421 ms 17296 KB Output is correct
2 Correct 14970 ms 17296 KB Output is correct
3 Correct 14809 ms 18880 KB Output is correct
4 Correct 14076 ms 17292 KB Output is correct
5 Correct 14170 ms 17296 KB Output is correct
6 Correct 107 ms 5492 KB Output is correct
7 Correct 107 ms 5488 KB Output is correct
8 Correct 112 ms 5552 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 5552 KB Output is correct
2 Correct 109 ms 5552 KB Output is correct
3 Correct 108 ms 5536 KB Output is correct
4 Correct 110 ms 5580 KB Output is correct
5 Correct 108 ms 5536 KB Output is correct
6 Correct 112 ms 5584 KB Output is correct
7 Correct 108 ms 5620 KB Output is correct
8 Correct 108 ms 5560 KB Output is correct
9 Correct 113 ms 5556 KB Output is correct
10 Correct 108 ms 5588 KB Output is correct
11 Correct 168 ms 6628 KB Output is correct
12 Correct 112 ms 5520 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3523 ms 5884 KB Output is correct
2 Correct 3469 ms 5964 KB Output is correct
3 Correct 3480 ms 5888 KB Output is correct
4 Correct 3492 ms 5888 KB Output is correct
5 Correct 3481 ms 5892 KB Output is correct
6 Correct 109 ms 5580 KB Output is correct
7 Correct 114 ms 5496 KB Output is correct
8 Correct 108 ms 5580 KB Output is correct
9 Correct 16997 ms 5888 KB Output is correct
10 Correct 242 ms 5580 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15478 ms 21208 KB Output is correct
2 Correct 15001 ms 21208 KB Output is correct
3 Correct 14018 ms 21208 KB Output is correct
4 Correct 14045 ms 21956 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3474 ms 5964 KB Output is correct
2 Correct 3459 ms 5892 KB Output is correct
3 Correct 3494 ms 5888 KB Output is correct
4 Correct 3471 ms 5964 KB Output is correct
5 Correct 3470 ms 5892 KB Output is correct
6 Correct 14024 ms 21212 KB Output is correct
7 Correct 14050 ms 21204 KB Output is correct
8 Correct 14030 ms 21208 KB Output is correct
9 Correct 14101 ms 21948 KB Output is correct
10 Correct 14256 ms 17300 KB Output is correct
11 Correct 13918 ms 17348 KB Output is correct
12 Correct 14006 ms 18828 KB Output is correct
13 Correct 13993 ms 17292 KB Output is correct
14 Correct 13983 ms 17292 KB Output is correct
15 Correct 109 ms 5448 KB Output is correct
16 Correct 108 ms 5540 KB Output is correct
17 Correct 108 ms 5452 KB Output is correct
18 Correct 106 ms 5580 KB Output is correct
19 Correct 107 ms 5628 KB Output is correct
20 Correct 111 ms 5520 KB Output is correct
21 Correct 107 ms 5580 KB Output is correct
22 Correct 107 ms 5588 KB Output is correct
23 Correct 107 ms 5588 KB Output is correct
24 Correct 114 ms 5612 KB Output is correct
25 Correct 169 ms 6548 KB Output is correct
26 Correct 108 ms 5632 KB Output is correct
27 Correct 16886 ms 5892 KB Output is correct
28 Execution timed out 20076 ms 21524 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3718 ms 5888 KB Output is correct
2 Correct 3642 ms 5892 KB Output is correct
3 Correct 3614 ms 5892 KB Output is correct
4 Correct 3625 ms 5888 KB Output is correct
5 Correct 3920 ms 5888 KB Output is correct
6 Correct 16152 ms 21208 KB Output is correct
7 Correct 16077 ms 21212 KB Output is correct
8 Correct 15105 ms 21204 KB Output is correct
9 Correct 15187 ms 22032 KB Output is correct
10 Correct 14126 ms 17288 KB Output is correct
11 Correct 14024 ms 17296 KB Output is correct
12 Correct 14001 ms 18832 KB Output is correct
13 Correct 14121 ms 17296 KB Output is correct
14 Correct 14993 ms 17292 KB Output is correct
15 Correct 1752 ms 21140 KB Output is correct
16 Execution timed out 20082 ms 30372 KB Time limit exceeded
17 Halted 0 ms 0 KB -