oj.uz

Submission #605685

# Submission time Handle Problem Language Result Execution time Memory
605685 2022-07-25T22:51:00 Z skittles1412 Wombats (IOI13_wombats) C++17
37 / 100
 17386 ms 21376 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;

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 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));
    for (int i = maxt; i < 2 * maxt; i++) {
        update_leaf(i);
    }
    for (int i = maxt - 1; i; i--) {
        v[i] = mul(v[i * 2], v[i * 2 + 1]);
    }
}

void update(int ind) {
    ind /= bsize;
    ind += maxt;
    update_leaf(ind);
    for (; ind > 1; ind >>= 1) {
        v[ind >> 1] = mul(v[ind], v[ind ^ 1]);
    }
}

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 14569 ms 17468 KB Output is correct
2 Correct 14544 ms 17468 KB Output is correct
3 Correct 14493 ms 18996 KB Output is correct
4 Correct 14344 ms 17564 KB Output is correct
5 Correct 14345 ms 17460 KB Output is correct
6 Correct 113 ms 13464 KB Output is correct
7 Correct 113 ms 13440 KB Output is correct
8 Correct 111 ms 13460 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 13448 KB Output is correct
2 Correct 127 ms 13624 KB Output is correct
3 Correct 110 ms 13508 KB Output is correct
4 Correct 119 ms 13516 KB Output is correct
5 Correct 122 ms 13528 KB Output is correct
6 Correct 136 ms 13564 KB Output is correct
7 Correct 116 ms 13480 KB Output is correct
8 Correct 114 ms 13500 KB Output is correct
9 Correct 112 ms 13568 KB Output is correct
10 Correct 118 ms 13480 KB Output is correct
11 Correct 177 ms 14512 KB Output is correct
12 Correct 111 ms 13480 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3644 ms 13708 KB Output is correct
2 Correct 3582 ms 13716 KB Output is correct
3 Correct 3541 ms 13800 KB Output is correct
4 Correct 3626 ms 13836 KB Output is correct
5 Correct 3617 ms 13712 KB Output is correct
6 Correct 118 ms 13540 KB Output is correct
7 Correct 114 ms 13540 KB Output is correct
8 Correct 117 ms 13512 KB Output is correct
9 Correct 17386 ms 13720 KB Output is correct
10 Correct 169 ms 13528 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 14603 ms 21368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3727 ms 13752 KB Output is correct
2 Correct 3548 ms 13716 KB Output is correct
3 Correct 3546 ms 13644 KB Output is correct
4 Correct 3670 ms 13720 KB Output is correct
5 Correct 3672 ms 13720 KB Output is correct
6 Incorrect 14504 ms 21376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3642 ms 13900 KB Output is correct
2 Correct 3682 ms 13824 KB Output is correct
3 Correct 3681 ms 13724 KB Output is correct
4 Correct 3661 ms 13724 KB Output is correct
5 Correct 3595 ms 13712 KB Output is correct
6 Incorrect 14358 ms 21376 KB Output isn't correct
7 Halted 0 ms 0 KB -