oj.uz

Submission #605714

# Submission time Handle Problem Language Result Execution time Memory
605714 2022-07-25T23:49:53 Z skittles1412 Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 23112 KB 
#pragma GCC optimize("Ofast", "unroll-loops")

#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) {
    static int cnt = 0;
    assert(++cnt <= 500);
    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 3375 ms 17464 KB Output is correct
2 Correct 3382 ms 17460 KB Output is correct
3 Correct 3405 ms 18996 KB Output is correct
4 Correct 3458 ms 17456 KB Output is correct
5 Correct 3534 ms 17456 KB Output is correct
6 Correct 33 ms 5716 KB Output is correct
7 Correct 29 ms 5656 KB Output is correct
8 Correct 28 ms 5676 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5648 KB Output is correct
2 Correct 38 ms 5716 KB Output is correct
3 Correct 29 ms 5680 KB Output is correct
4 Correct 28 ms 5700 KB Output is correct
5 Correct 28 ms 5768 KB Output is correct
6 Correct 30 ms 5676 KB Output is correct
7 Correct 27 ms 5732 KB Output is correct
8 Correct 31 ms 5712 KB Output is correct
9 Correct 27 ms 5716 KB Output is correct
10 Correct 31 ms 5724 KB Output is correct
11 Correct 93 ms 6692 KB Output is correct
12 Correct 27 ms 5796 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1122 ms 6052 KB Output is correct
2 Correct 1119 ms 6052 KB Output is correct
3 Correct 1140 ms 6048 KB Output is correct
4 Correct 1088 ms 6056 KB Output is correct
5 Correct 1133 ms 6056 KB Output is correct
6 Correct 28 ms 5708 KB Output is correct
7 Correct 27 ms 5708 KB Output is correct
8 Correct 27 ms 5708 KB Output is correct
9 Correct 5370 ms 6056 KB Output is correct
10 Correct 55 ms 5648 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3516 ms 21492 KB Output is correct
2 Correct 3379 ms 21456 KB Output is correct
3 Correct 3416 ms 21392 KB Output is correct
4 Correct 3449 ms 22140 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1087 ms 6052 KB Output is correct
2 Correct 1109 ms 6048 KB Output is correct
3 Correct 1113 ms 6048 KB Output is correct
4 Correct 1116 ms 6172 KB Output is correct
5 Correct 1075 ms 6052 KB Output is correct
6 Correct 3238 ms 21376 KB Output is correct
7 Correct 3297 ms 21424 KB Output is correct
8 Correct 3269 ms 21372 KB Output is correct
9 Correct 3329 ms 22184 KB Output is correct
10 Correct 3229 ms 17464 KB Output is correct
11 Correct 3238 ms 17460 KB Output is correct
12 Correct 3279 ms 18968 KB Output is correct
13 Correct 3250 ms 17460 KB Output is correct
14 Correct 3233 ms 17464 KB Output is correct
15 Correct 28 ms 5708 KB Output is correct
16 Correct 27 ms 5708 KB Output is correct
17 Correct 27 ms 5672 KB Output is correct
18 Correct 27 ms 5772 KB Output is correct
19 Correct 27 ms 5716 KB Output is correct
20 Correct 27 ms 5784 KB Output is correct
21 Correct 28 ms 5776 KB Output is correct
22 Correct 27 ms 5688 KB Output is correct
23 Correct 28 ms 5732 KB Output is correct
24 Correct 29 ms 5784 KB Output is correct
25 Correct 91 ms 6836 KB Output is correct
26 Correct 28 ms 5780 KB Output is correct
27 Correct 5217 ms 6052 KB Output is correct
28 Correct 9537 ms 21964 KB Output is correct
29 Correct 9840 ms 19252 KB Output is correct
30 Correct 9446 ms 19228 KB Output is correct
31 Correct 9904 ms 22844 KB Output is correct
32 Correct 41 ms 5716 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1080 ms 6060 KB Output is correct
2 Correct 1059 ms 6052 KB Output is correct
3 Correct 1061 ms 6092 KB Output is correct
4 Correct 1074 ms 6048 KB Output is correct
5 Correct 1053 ms 6060 KB Output is correct
6 Correct 3231 ms 21452 KB Output is correct
7 Correct 3262 ms 21580 KB Output is correct
8 Correct 3236 ms 21372 KB Output is correct
9 Correct 3291 ms 22332 KB Output is correct
10 Correct 3309 ms 17456 KB Output is correct
11 Correct 3276 ms 17460 KB Output is correct
12 Correct 3291 ms 19116 KB Output is correct
13 Correct 3276 ms 17460 KB Output is correct
14 Correct 3293 ms 17460 KB Output is correct
15 Correct 1108 ms 21372 KB Output is correct
16 Execution timed out 20102 ms 23112 KB Time limit exceeded
17 Halted 0 ms 0 KB -