oj.uz

Submission #605719

# Submission time Handle Problem Language Result Execution time Memory
605719 2022-07-26T00:21:34 Z skittles1412 Wombats (IOI13_wombats) C++17
100 / 100
 11933 ms 65260 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#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 = 5000, maxm = 200, bsize = 40, maxt = 128;
// 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) {
    static_assert(C % 8 == 0);
    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 3426 ms 52268 KB Output is correct
2 Correct 3180 ms 52268 KB Output is correct
3 Correct 3259 ms 53800 KB Output is correct
4 Correct 3199 ms 52268 KB Output is correct
5 Correct 3168 ms 52260 KB Output is correct
6 Correct 126 ms 40524 KB Output is correct
7 Correct 142 ms 40524 KB Output is correct
8 Correct 129 ms 40520 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 40512 KB Output is correct
2 Correct 130 ms 40452 KB Output is correct
3 Correct 129 ms 40512 KB Output is correct
4 Correct 131 ms 40516 KB Output is correct
5 Correct 127 ms 40516 KB Output is correct
6 Correct 130 ms 40492 KB Output is correct
7 Correct 134 ms 40488 KB Output is correct
8 Correct 133 ms 40500 KB Output is correct
9 Correct 140 ms 40600 KB Output is correct
10 Correct 128 ms 40600 KB Output is correct
11 Correct 193 ms 41564 KB Output is correct
12 Correct 133 ms 40540 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1134 ms 40852 KB Output is correct
2 Correct 1323 ms 40852 KB Output is correct
3 Correct 1291 ms 40948 KB Output is correct
4 Correct 1283 ms 40856 KB Output is correct
5 Correct 1329 ms 40956 KB Output is correct
6 Correct 128 ms 40524 KB Output is correct
7 Correct 127 ms 40496 KB Output is correct
8 Correct 127 ms 40468 KB Output is correct
9 Correct 6057 ms 40940 KB Output is correct
10 Correct 143 ms 40444 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3226 ms 56212 KB Output is correct
2 Correct 3207 ms 56180 KB Output is correct
3 Correct 3213 ms 56060 KB Output is correct
4 Correct 3246 ms 57040 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1138 ms 40780 KB Output is correct
2 Correct 1315 ms 40908 KB Output is correct
3 Correct 1263 ms 40852 KB Output is correct
4 Correct 1286 ms 40960 KB Output is correct
5 Correct 1328 ms 40852 KB Output is correct
6 Correct 3212 ms 56248 KB Output is correct
7 Correct 3199 ms 56172 KB Output is correct
8 Correct 3243 ms 56300 KB Output is correct
9 Correct 3231 ms 57396 KB Output is correct
10 Correct 3217 ms 52300 KB Output is correct
11 Correct 3180 ms 52264 KB Output is correct
12 Correct 3256 ms 53836 KB Output is correct
13 Correct 3229 ms 52224 KB Output is correct
14 Correct 3231 ms 52264 KB Output is correct
15 Correct 129 ms 40524 KB Output is correct
16 Correct 128 ms 40452 KB Output is correct
17 Correct 129 ms 40464 KB Output is correct
18 Correct 130 ms 40524 KB Output is correct
19 Correct 139 ms 40656 KB Output is correct
20 Correct 138 ms 40504 KB Output is correct
21 Correct 129 ms 40508 KB Output is correct
22 Correct 134 ms 40540 KB Output is correct
23 Correct 132 ms 40584 KB Output is correct
24 Correct 131 ms 40516 KB Output is correct
25 Correct 192 ms 41596 KB Output is correct
26 Correct 128 ms 40560 KB Output is correct
27 Correct 6094 ms 41000 KB Output is correct
28 Correct 6840 ms 56396 KB Output is correct
29 Correct 6753 ms 54004 KB Output is correct
30 Correct 6731 ms 53732 KB Output is correct
31 Correct 6926 ms 57748 KB Output is correct
32 Correct 142 ms 40460 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1156 ms 40980 KB Output is correct
2 Correct 1333 ms 40848 KB Output is correct
3 Correct 1280 ms 40860 KB Output is correct
4 Correct 1278 ms 40888 KB Output is correct
5 Correct 1333 ms 40860 KB Output is correct
6 Correct 3221 ms 56300 KB Output is correct
7 Correct 3266 ms 56268 KB Output is correct
8 Correct 3271 ms 56172 KB Output is correct
9 Correct 3300 ms 57060 KB Output is correct
10 Correct 3228 ms 52260 KB Output is correct
11 Correct 3237 ms 52384 KB Output is correct
12 Correct 3245 ms 53800 KB Output is correct
13 Correct 3199 ms 52172 KB Output is correct
14 Correct 3175 ms 52264 KB Output is correct
15 Correct 2043 ms 56116 KB Output is correct
16 Correct 11811 ms 58112 KB Output is correct
17 Correct 129 ms 40544 KB Output is correct
18 Correct 133 ms 40472 KB Output is correct
19 Correct 129 ms 40636 KB Output is correct
20 Correct 129 ms 40524 KB Output is correct
21 Correct 130 ms 40568 KB Output is correct
22 Correct 151 ms 40628 KB Output is correct
23 Correct 131 ms 40628 KB Output is correct
24 Correct 129 ms 40492 KB Output is correct
25 Correct 130 ms 40564 KB Output is correct
26 Correct 137 ms 40524 KB Output is correct
27 Correct 195 ms 42868 KB Output is correct
28 Correct 132 ms 40500 KB Output is correct
29 Correct 6093 ms 40928 KB Output is correct
30 Correct 6896 ms 60512 KB Output is correct
31 Correct 11729 ms 64704 KB Output is correct
32 Correct 11807 ms 64564 KB Output is correct
33 Correct 6754 ms 57244 KB Output is correct
34 Correct 11407 ms 61160 KB Output is correct
35 Correct 6690 ms 57428 KB Output is correct
36 Correct 11362 ms 61372 KB Output is correct
37 Correct 6912 ms 62092 KB Output is correct
38 Correct 11750 ms 65260 KB Output is correct
39 Correct 140 ms 40524 KB Output is correct
40 Correct 11933 ms 61452 KB Output is correct