oj.uz

Submission #356666

# Submission time Handle Problem Language Result Execution time Memory
356666 2021-01-23T13:54:01 Z hamerin Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 262148 KB 
#include "wombats.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

const int L = 5;
const int pinf = numeric_limits<int>::max() / 2;
const int ninf = numeric_limits<int>::min() / 2;

int R, C;
vector<vector<int>> H, V;

namespace DPHelper {
    vector<vector<int>> base_get(int r, bool fv = true) {
        vector<vector<int>> ret(C, vector<int>(C, pinf));
        for (int k = 0; k < C; k++) {
            for (int i = 0; i < C - k; i++) {
                if (k == 0)
                    ret[i][i] = 0;
                else
                    ret[i][i + k] = ret[i + k][i] = ret[i + 1][i + k] + H[r][i];
            }
        }

        if (fv) {
            for (int i = 0; i < C; i++)
                for (int j = 0; j < C; j++)
                    ret[i][j] += V[r][j];
        }

        return ret;
    }

    vector<vector<int>> mer(const vector<vector<int>>& lhs, const vector<vector<int>>& rhs) {
        vector<vector<int>> ret(C, vector<int>(C, pinf));
        vector<vector<int>> opt(C, vector<int>(C));

        for (int k = 0; k < C; k++) {
            for (int i = 0; i < C - k; i++) {
                if (k == 0) {
                    for (int j = 0; j < C; j++) {
                        if (ret[i][i] > lhs[i][j] + rhs[j][i]) {
                            ret[i][i] = lhs[i][j] + rhs[j][i];
                            opt[i][i] = j;
                        }
                    }
                } else {
                    for (int j = opt[i][i + k - 1]; j <= opt[i + 1][i + k]; j++) {
                        if (ret[i][i + k] > lhs[i][j] + rhs[j][i + k]) {
                            ret[i][i + k] = lhs[i][j] + rhs[j][i + k];
                            opt[i][i + k] = j;
                        }
                    }
                    for (int j = opt[i + k - 1][i]; j <= opt[i + k][i + 1]; j++) {
                        if (ret[i + k][i] > lhs[i + k][j] + rhs[j][i]) {
                            ret[i + k][i] = lhs[i + k][j] + rhs[j][i];
                            opt[i + k][i] = j;
                        }
                    }
                }
            }
        }

        return ret;
    }

    vector<vector<int>> base_solve(int s, int e) {
        auto ret = base_get(s);

        for (int r = s + 1; r <= e; r++)
            ret = mer(ret, base_get(r));

        return ret;
    }
};  // namespace DPHelper

class SegTree {
   public:
    int N{};
    vector<vector<vector<int>>> vl;

    SegTree() = default;

    SegTree(int N) {
        this->N = N;
        vl.resize(N << 2);
    }

    void init(int s, int e, int n) {
        if (e - s < L) {
            vl[n] = DPHelper::base_solve(s, e);
            return;
        }

        int m = (s + e) >> 1, k = n << 1;
        init(s, m, k);
        init(m + 1, e, k | 1);

        vl[n] = DPHelper::mer(vl[k], vl[k | 1]);
    }

    inline void init() {
        init(0, N - 2, 1);
    }

    void update(int s, int e, int n, int p) {
        if (e < p || p < s) return;
        if (e - s < L) {
            vl[n] = DPHelper::base_solve(s, e);
            return;
        }

        int m = (s + e) >> 1, k = n << 1;
        update(s, m, k, p);
        update(m + 1, e, k | 1, p);

        vl[n] = DPHelper::mer(vl[k], vl[k | 1]);
    }

    inline void update(int p) {
        update(0, N - 2, 1, p);
    }

    vector<vector<int>> query() {
        return DPHelper::mer(vl[1], DPHelper::base_get(N - 1, false));
    }
};

SegTree ST;

void init(int r, int c, int h[5000][200], int v[5000][200]) {
    R = r, C = c;
    H.resize(R);
    V.resize(R - 1);

    for (int i = 0; i < R; i++) copy(h[i], h[i] + C - 1, back_inserter(H[i]));
    for (int i = 0; i < R - 1; i++) copy(v[i], v[i] + C, back_inserter(V[i]));

    ST = SegTree(R);
    ST.init();
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;
    ST.update(P);
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    ST.update(P);
}

int escape(int V1, int V2) {
    return ST.query()[V1][V2];
}

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 7 ms 5228 KB Output is correct
2 Correct 7 ms 5228 KB Output is correct
3 Correct 133 ms 6892 KB Output is correct
4 Correct 7 ms 5228 KB Output is correct
5 Correct 7 ms 5228 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 4 ms 364 KB Output is correct
5 Correct 4 ms 364 KB Output is correct
6 Correct 4 ms 364 KB Output is correct
7 Correct 4 ms 364 KB Output is correct
8 Correct 4 ms 364 KB Output is correct
9 Correct 4 ms 364 KB Output is correct
10 Correct 4 ms 364 KB Output is correct
11 Correct 1640 ms 1424 KB Output is correct
12 Correct 5 ms 364 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 3564 KB Output is correct
2 Correct 144 ms 3564 KB Output is correct
3 Correct 197 ms 3692 KB Output is correct
4 Correct 190 ms 3564 KB Output is correct
5 Correct 192 ms 3436 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 652 ms 3580 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9452 KB Output is correct
2 Correct 13 ms 9452 KB Output is correct
3 Correct 13 ms 9452 KB Output is correct
4 Correct 90 ms 10232 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 3576 KB Output is correct
2 Correct 148 ms 3436 KB Output is correct
3 Correct 196 ms 3692 KB Output is correct
4 Correct 196 ms 3564 KB Output is correct
5 Correct 193 ms 3564 KB Output is correct
6 Correct 12 ms 9452 KB Output is correct
7 Correct 12 ms 9452 KB Output is correct
8 Correct 13 ms 9452 KB Output is correct
9 Correct 86 ms 10228 KB Output is correct
10 Correct 7 ms 5228 KB Output is correct
11 Correct 7 ms 5228 KB Output is correct
12 Correct 130 ms 6892 KB Output is correct
13 Correct 7 ms 5248 KB Output is correct
14 Correct 7 ms 5228 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 4 ms 364 KB Output is correct
19 Correct 4 ms 364 KB Output is correct
20 Correct 4 ms 364 KB Output is correct
21 Correct 4 ms 364 KB Output is correct
22 Correct 3 ms 364 KB Output is correct
23 Correct 4 ms 364 KB Output is correct
24 Correct 4 ms 364 KB Output is correct
25 Correct 1628 ms 1388 KB Output is correct
26 Correct 4 ms 364 KB Output is correct
27 Correct 599 ms 3704 KB Output is correct
28 Correct 11462 ms 103372 KB Output is correct
29 Correct 13541 ms 100884 KB Output is correct
30 Correct 12670 ms 100980 KB Output is correct
31 Execution timed out 20087 ms 103548 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 3692 KB Output is correct
2 Correct 145 ms 3656 KB Output is correct
3 Correct 192 ms 3692 KB Output is correct
4 Correct 193 ms 3692 KB Output is correct
5 Correct 209 ms 3436 KB Output is correct
6 Correct 13 ms 9452 KB Output is correct
7 Correct 13 ms 9452 KB Output is correct
8 Correct 13 ms 9452 KB Output is correct
9 Correct 89 ms 10348 KB Output is correct
10 Correct 7 ms 5228 KB Output is correct
11 Correct 7 ms 5228 KB Output is correct
12 Correct 128 ms 6892 KB Output is correct
13 Correct 7 ms 5228 KB Output is correct
14 Correct 7 ms 5228 KB Output is correct
15 Runtime error 2959 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -