oj.uz

Submission #1067821

# Submission time Handle Problem Language Result Execution time Memory
1067821 2024-08-21T03:57:33 Z Plurm Wombats (IOI13_wombats) C++11
76 / 100
 20000 ms 33236 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

int block_size;
int num_blocks;
int global_H[5000][200];
int global_V[5000][200];
int qsr[5000][200];
int C;
class BlockAnswer {
  public:
    vector<vector<int>> ans;
    int rs, rt;
    BlockAnswer(int r1, int r2) {
        rs = r1;
        rt = r2;
        ans.resize(C);
        for (int i = 0; i < C; i++) {
            ans[i].resize(C, 1000000000);
        }
    }
    virtual void update_i(int col) {
        vector<int> dpst;
        dpst.resize(C, 1000000000);
        dpst[col] = 0;
        for (int row = rs; row <= rt; row++) {
            vector<int> dpnw;
            dpnw.resize(C, 1000000000);
            int pref = 1000000000;
            for (int nc = 0; nc < C; nc++) {
                pref = min(pref, dpst[nc] - qsr[row][nc]);
                dpnw[nc] =
                    min(dpnw[nc], pref + qsr[row][nc] + global_V[row][nc]);
            }
            pref = 1000000000;
            for (int nc = C - 1; nc >= 0; nc--) {
                pref = min(pref, dpst[nc] + qsr[row][nc]);
                dpnw[nc] =
                    min(dpnw[nc], pref - qsr[row][nc] + global_V[row][nc]);
            }
            swap(dpst, dpnw);
        }
        ans[col] = dpst;
    }
    void update() {
        for (int i = 0; i < C; i++) {
            update_i(i);
        }
    }
};
vector<BlockAnswer> blans;
void dcopt(vector<int> &dpnw, vector<int> &dpst, vector<vector<int>> &cost,
           int ltarget, int rtarget, int lfound, int rfound) {
    if (ltarget > rtarget)
        return;
    int mid = (ltarget + rtarget) / 2;
    int idx = -1;
    for (int oc = lfound; oc <= rfound; oc++) {
        if (dpst[oc] + cost[oc][mid] < dpnw[mid]) {
            dpnw[mid] = dpst[oc] + cost[oc][mid];
            idx = oc;
        }
    }
    dcopt(dpnw, dpst, cost, ltarget, mid - 1, lfound, idx);
    dcopt(dpnw, dpst, cost, mid + 1, rtarget, idx, rfound);
}
class GlobalAnswer : public BlockAnswer {
  public:
    GlobalAnswer() : BlockAnswer(0, 0) {}
    void update_i(int col) override {
        vector<int> dpst;
        dpst.resize(C, 1000000000);
        dpst[col] = 0;
        for (int blk = 0; blk < num_blocks; blk++) {
            vector<int> dpnw;
            dpnw.resize(C, 1000000000);
            // DC opt?
            dcopt(dpnw, dpst, blans[blk].ans, 0, C - 1, 0, C - 1);
            swap(dpst, dpnw);
        }
        ans[col] = dpst;
    }
};
GlobalAnswer *glob;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    block_size = sqrt(R * max(1.0, log2(C)));
    num_blocks = (R + block_size - 1) / block_size;
    ::C = C;
    memcpy(global_H, H, 5000 * 200 * 4);
    memcpy(global_V, V, 5000 * 200 * 4);
    for (int j = 0; j < C; j++)
        global_V[R - 1][j] = 0;
    for (int j = 0; j < R; j++) {
        qsr[j][0] = 0;
        for (int i = 0; i < C - 1; i++) {
            qsr[j][i + 1] = qsr[j][i] + global_H[j][i];
        }
    }
    for (int i = 0; i < num_blocks; i++) {
        int r1 = i * block_size;
        int r2 = min((i + 1) * block_size - 1, R - 1);
        blans.emplace_back(r1, r2);
        blans.back().update();
    }
    glob = new GlobalAnswer();
    glob->update();
}

void changeH(int P, int Q, int W) {
    global_H[P][Q] = W;
    for (int i = 0; i < C - 1; i++) {
        qsr[P][i + 1] = qsr[P][i] + global_H[P][i];
    }
    blans[P / block_size].update();
    glob->update();
}

void changeV(int P, int Q, int W) {
    global_V[P][Q] = W;
    blans[P / block_size].update();
    glob->update();
}

int escape(int V1, int V2) { return glob->ans[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 10 ms 15960 KB Output is correct
2 Correct 8 ms 15964 KB Output is correct
3 Correct 43 ms 18768 KB Output is correct
4 Correct 9 ms 15964 KB Output is correct
5 Correct 9 ms 15948 KB Output is correct
6 Correct 4 ms 8284 KB Output is correct
7 Correct 4 ms 8284 KB Output is correct
8 Correct 4 ms 8284 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 4 ms 8096 KB Output is correct
3 Correct 4 ms 8156 KB Output is correct
4 Correct 4 ms 8184 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 4 ms 8284 KB Output is correct
7 Correct 5 ms 8284 KB Output is correct
8 Correct 4 ms 8208 KB Output is correct
9 Correct 4 ms 8136 KB Output is correct
10 Correct 4 ms 8284 KB Output is correct
11 Correct 41 ms 10564 KB Output is correct
12 Correct 5 ms 8284 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 8788 KB Output is correct
2 Correct 126 ms 8540 KB Output is correct
3 Correct 124 ms 8720 KB Output is correct
4 Correct 123 ms 8540 KB Output is correct
5 Correct 126 ms 8716 KB Output is correct
6 Correct 4 ms 8284 KB Output is correct
7 Correct 4 ms 8284 KB Output is correct
8 Correct 4 ms 8128 KB Output is correct
9 Correct 561 ms 8796 KB Output is correct
10 Correct 4 ms 8284 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19804 KB Output is correct
2 Correct 14 ms 19804 KB Output is correct
3 Correct 13 ms 19804 KB Output is correct
4 Correct 31 ms 20688 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 8540 KB Output is correct
2 Correct 120 ms 8536 KB Output is correct
3 Correct 127 ms 8540 KB Output is correct
4 Correct 123 ms 8536 KB Output is correct
5 Correct 121 ms 8712 KB Output is correct
6 Correct 12 ms 19800 KB Output is correct
7 Correct 13 ms 19800 KB Output is correct
8 Correct 13 ms 19804 KB Output is correct
9 Correct 37 ms 20560 KB Output is correct
10 Correct 9 ms 16104 KB Output is correct
11 Correct 8 ms 16056 KB Output is correct
12 Correct 46 ms 18772 KB Output is correct
13 Correct 11 ms 15960 KB Output is correct
14 Correct 8 ms 15960 KB Output is correct
15 Correct 4 ms 8284 KB Output is correct
16 Correct 4 ms 8284 KB Output is correct
17 Correct 4 ms 8284 KB Output is correct
18 Correct 4 ms 8132 KB Output is correct
19 Correct 5 ms 8296 KB Output is correct
20 Correct 7 ms 8284 KB Output is correct
21 Correct 4 ms 8284 KB Output is correct
22 Correct 4 ms 8180 KB Output is correct
23 Correct 4 ms 8340 KB Output is correct
24 Correct 5 ms 8284 KB Output is correct
25 Correct 41 ms 10692 KB Output is correct
26 Correct 4 ms 8280 KB Output is correct
27 Correct 576 ms 8796 KB Output is correct
28 Correct 4312 ms 25172 KB Output is correct
29 Correct 4117 ms 22648 KB Output is correct
30 Correct 4011 ms 22608 KB Output is correct
31 Correct 4509 ms 24984 KB Output is correct
32 Correct 5 ms 8280 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 8540 KB Output is correct
2 Correct 120 ms 8716 KB Output is correct
3 Correct 125 ms 8540 KB Output is correct
4 Correct 132 ms 8540 KB Output is correct
5 Correct 129 ms 8540 KB Output is correct
6 Correct 13 ms 19804 KB Output is correct
7 Correct 12 ms 20024 KB Output is correct
8 Correct 13 ms 19804 KB Output is correct
9 Correct 31 ms 20712 KB Output is correct
10 Correct 8 ms 15964 KB Output is correct
11 Correct 8 ms 15964 KB Output is correct
12 Correct 50 ms 18276 KB Output is correct
13 Correct 9 ms 15964 KB Output is correct
14 Correct 9 ms 15920 KB Output is correct
15 Correct 819 ms 29656 KB Output is correct
16 Correct 19514 ms 27452 KB Output is correct
17 Correct 4 ms 8280 KB Output is correct
18 Correct 4 ms 8284 KB Output is correct
19 Correct 4 ms 8136 KB Output is correct
20 Correct 4 ms 8284 KB Output is correct
21 Correct 5 ms 8284 KB Output is correct
22 Correct 5 ms 8284 KB Output is correct
23 Correct 4 ms 8284 KB Output is correct
24 Correct 4 ms 8284 KB Output is correct
25 Correct 4 ms 8280 KB Output is correct
26 Correct 4 ms 8284 KB Output is correct
27 Correct 44 ms 10644 KB Output is correct
28 Correct 5 ms 8284 KB Output is correct
29 Correct 571 ms 8796 KB Output is correct
30 Correct 4390 ms 25356 KB Output is correct
31 Correct 18311 ms 32796 KB Output is correct
32 Correct 18621 ms 32676 KB Output is correct
33 Correct 4146 ms 22804 KB Output is correct
34 Correct 17666 ms 29840 KB Output is correct
35 Correct 4075 ms 22636 KB Output is correct
36 Correct 17860 ms 29780 KB Output is correct
37 Correct 4638 ms 27000 KB Output is correct
38 Correct 18692 ms 33236 KB Output is correct
39 Correct 5 ms 8284 KB Output is correct
40 Execution timed out 20082 ms 29960 KB Time limit exceeded
41 Halted 0 ms 0 KB -