oj.uz

Submission #1067816

# Submission time Handle Problem Language Result Execution time Memory
1067816 2024-08-21T03:53:28 Z Plurm Wombats (IOI13_wombats) C++11
55 / 100
 20000 ms 41736 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 = 0; oc < C; 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);
    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 9 ms 15960 KB Output is correct
2 Correct 10 ms 15964 KB Output is correct
3 Correct 50 ms 18692 KB Output is correct
4 Correct 9 ms 15964 KB Output is correct
5 Correct 9 ms 15964 KB Output is correct
6 Correct 4 ms 8280 KB Output is correct
7 Correct 4 ms 8212 KB Output is correct
8 Correct 3 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 8284 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 5 ms 8280 KB Output is correct
5 Correct 5 ms 8284 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
9 Correct 5 ms 8284 KB Output is correct
10 Correct 4 ms 8136 KB Output is correct
11 Correct 48 ms 10564 KB Output is correct
12 Correct 6 ms 8284 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1247 ms 9096 KB Output is correct
2 Correct 1038 ms 9052 KB Output is correct
3 Correct 1125 ms 9052 KB Output is correct
4 Correct 1117 ms 9060 KB Output is correct
5 Correct 1086 ms 9052 KB Output is correct
6 Correct 4 ms 8280 KB Output is correct
7 Correct 4 ms 8284 KB Output is correct
8 Correct 4 ms 8284 KB Output is correct
9 Correct 4598 ms 9056 KB Output is correct
10 Correct 5 ms 8280 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20060 KB Output is correct
2 Correct 12 ms 20060 KB Output is correct
3 Correct 14 ms 19908 KB Output is correct
4 Correct 33 ms 21340 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1235 ms 9052 KB Output is correct
2 Correct 1036 ms 9052 KB Output is correct
3 Correct 1127 ms 9060 KB Output is correct
4 Correct 1124 ms 9060 KB Output is correct
5 Correct 1132 ms 9052 KB Output is correct
6 Correct 14 ms 20060 KB Output is correct
7 Correct 19 ms 20080 KB Output is correct
8 Correct 15 ms 20056 KB Output is correct
9 Correct 44 ms 21300 KB Output is correct
10 Correct 8 ms 15964 KB Output is correct
11 Correct 8 ms 15956 KB Output is correct
12 Correct 47 ms 18696 KB Output is correct
13 Correct 10 ms 15964 KB Output is correct
14 Correct 9 ms 15896 KB Output is correct
15 Correct 5 ms 8284 KB Output is correct
16 Correct 4 ms 8284 KB Output is correct
17 Correct 3 ms 8284 KB Output is correct
18 Correct 4 ms 8284 KB Output is correct
19 Correct 5 ms 8160 KB Output is correct
20 Correct 5 ms 8284 KB Output is correct
21 Correct 4 ms 8280 KB Output is correct
22 Correct 4 ms 8284 KB Output is correct
23 Correct 5 ms 8160 KB Output is correct
24 Correct 4 ms 8280 KB Output is correct
25 Correct 44 ms 10624 KB Output is correct
26 Correct 4 ms 8284 KB Output is correct
27 Correct 4641 ms 9064 KB Output is correct
28 Execution timed out 20025 ms 26960 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1317 ms 9048 KB Output is correct
2 Correct 1042 ms 9088 KB Output is correct
3 Correct 1197 ms 9052 KB Output is correct
4 Correct 1162 ms 9048 KB Output is correct
5 Correct 1093 ms 9300 KB Output is correct
6 Correct 13 ms 20060 KB Output is correct
7 Correct 14 ms 20060 KB Output is correct
8 Correct 12 ms 20060 KB Output is correct
9 Correct 41 ms 21332 KB Output is correct
10 Correct 9 ms 15964 KB Output is correct
11 Correct 9 ms 15964 KB Output is correct
12 Correct 46 ms 18756 KB Output is correct
13 Correct 10 ms 15964 KB Output is correct
14 Correct 9 ms 15960 KB Output is correct
15 Correct 3586 ms 41736 KB Output is correct
16 Execution timed out 20012 ms 40020 KB Time limit exceeded
17 Halted 0 ms 0 KB -