oj.uz

Submission #605712

# Submission time Handle Problem Language Result Execution time Memory
605712 2022-07-25T23:47:55 Z skittles1412 Wombats (IOI13_wombats) C++17
76 / 100
 6784 ms 32324 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 = 105, 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 474 ms 13452 KB Output is correct
2 Correct 468 ms 13456 KB Output is correct
3 Correct 525 ms 14992 KB Output is correct
4 Correct 499 ms 13396 KB Output is correct
5 Correct 503 ms 13452 KB Output is correct
6 Correct 5 ms 1640 KB Output is correct
7 Correct 5 ms 1748 KB Output is correct
8 Correct 5 ms 1728 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1704 KB Output is correct
2 Correct 4 ms 1748 KB Output is correct
3 Correct 4 ms 1748 KB Output is correct
4 Correct 5 ms 1768 KB Output is correct
5 Correct 5 ms 1748 KB Output is correct
6 Correct 5 ms 1748 KB Output is correct
7 Correct 5 ms 1748 KB Output is correct
8 Correct 8 ms 1716 KB Output is correct
9 Correct 5 ms 1748 KB Output is correct
10 Correct 5 ms 1748 KB Output is correct
11 Correct 70 ms 2772 KB Output is correct
12 Correct 4 ms 1748 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 2044 KB Output is correct
2 Correct 473 ms 2036 KB Output is correct
3 Correct 492 ms 2040 KB Output is correct
4 Correct 516 ms 2044 KB Output is correct
5 Correct 484 ms 2048 KB Output is correct
6 Correct 6 ms 1748 KB Output is correct
7 Correct 5 ms 1748 KB Output is correct
8 Correct 4 ms 1748 KB Output is correct
9 Correct 2384 ms 2048 KB Output is correct
10 Correct 7 ms 1748 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 17376 KB Output is correct
2 Correct 494 ms 17360 KB Output is correct
3 Correct 490 ms 17364 KB Output is correct
4 Correct 515 ms 18124 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 2044 KB Output is correct
2 Correct 460 ms 2036 KB Output is correct
3 Correct 497 ms 2004 KB Output is correct
4 Correct 461 ms 2044 KB Output is correct
5 Correct 498 ms 2056 KB Output is correct
6 Correct 485 ms 17484 KB Output is correct
7 Correct 467 ms 17368 KB Output is correct
8 Correct 492 ms 17364 KB Output is correct
9 Correct 503 ms 18124 KB Output is correct
10 Correct 479 ms 13452 KB Output is correct
11 Correct 496 ms 13464 KB Output is correct
12 Correct 517 ms 15020 KB Output is correct
13 Correct 468 ms 13468 KB Output is correct
14 Correct 525 ms 13452 KB Output is correct
15 Correct 6 ms 1748 KB Output is correct
16 Correct 4 ms 1748 KB Output is correct
17 Correct 4 ms 1748 KB Output is correct
18 Correct 4 ms 1748 KB Output is correct
19 Correct 6 ms 1748 KB Output is correct
20 Correct 5 ms 1796 KB Output is correct
21 Correct 5 ms 1748 KB Output is correct
22 Correct 5 ms 1760 KB Output is correct
23 Correct 5 ms 1748 KB Output is correct
24 Correct 4 ms 1748 KB Output is correct
25 Correct 67 ms 2764 KB Output is correct
26 Correct 5 ms 1748 KB Output is correct
27 Correct 2332 ms 2056 KB Output is correct
28 Correct 6371 ms 17868 KB Output is correct
29 Correct 6676 ms 18520 KB Output is correct
30 Correct 6415 ms 18696 KB Output is correct
31 Correct 6784 ms 23424 KB Output is correct
32 Correct 6 ms 1748 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 2048 KB Output is correct
2 Correct 468 ms 2044 KB Output is correct
3 Correct 473 ms 2084 KB Output is correct
4 Correct 461 ms 1956 KB Output is correct
5 Correct 518 ms 2128 KB Output is correct
6 Correct 486 ms 17492 KB Output is correct
7 Correct 476 ms 17372 KB Output is correct
8 Correct 498 ms 17492 KB Output is correct
9 Correct 520 ms 18160 KB Output is correct
10 Correct 474 ms 13460 KB Output is correct
11 Correct 498 ms 13452 KB Output is correct
12 Correct 554 ms 14984 KB Output is correct
13 Correct 472 ms 13456 KB Output is correct
14 Correct 462 ms 13452 KB Output is correct
15 Runtime error 185 ms 32324 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -