oj.uz

Submission #1067817

# Submission time Handle Problem Language Result Execution time Memory
1067817 2024-08-21T03:54:58 Z Plurm Wombats (IOI13_wombats) C++11
76 / 100
 20000 ms 41012 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);
    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 48 ms 18772 KB Output is correct
4 Correct 9 ms 15964 KB Output is correct
5 Correct 11 ms 15964 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 8280 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 4 ms 8284 KB Output is correct
5 Correct 5 ms 8208 KB Output is correct
6 Correct 5 ms 8136 KB Output is correct
7 Correct 5 ms 8284 KB Output is correct
8 Correct 5 ms 8284 KB Output is correct
9 Correct 5 ms 8280 KB Output is correct
10 Correct 4 ms 8132 KB Output is correct
11 Correct 43 ms 10664 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 183 ms 9072 KB Output is correct
2 Correct 170 ms 9300 KB Output is correct
3 Correct 180 ms 9304 KB Output is correct
4 Correct 167 ms 9056 KB Output is correct
5 Correct 163 ms 9048 KB Output is correct
6 Correct 5 ms 8284 KB Output is correct
7 Correct 4 ms 8136 KB Output is correct
8 Correct 4 ms 8280 KB Output is correct
9 Correct 694 ms 9048 KB Output is correct
10 Correct 4 ms 8280 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20096 KB Output is correct
2 Correct 13 ms 20060 KB Output is correct
3 Correct 12 ms 19912 KB Output is correct
4 Correct 32 ms 21332 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 8992 KB Output is correct
2 Correct 168 ms 9052 KB Output is correct
3 Correct 168 ms 9060 KB Output is correct
4 Correct 166 ms 9056 KB Output is correct
5 Correct 160 ms 9052 KB Output is correct
6 Correct 13 ms 20060 KB Output is correct
7 Correct 18 ms 20060 KB Output is correct
8 Correct 13 ms 20056 KB Output is correct
9 Correct 32 ms 21380 KB Output is correct
10 Correct 8 ms 15964 KB Output is correct
11 Correct 8 ms 15964 KB Output is correct
12 Correct 45 ms 18760 KB Output is correct
13 Correct 10 ms 15964 KB Output is correct
14 Correct 9 ms 16000 KB Output is correct
15 Correct 5 ms 8132 KB Output is correct
16 Correct 5 ms 8128 KB Output is correct
17 Correct 4 ms 8280 KB Output is correct
18 Correct 5 ms 8284 KB Output is correct
19 Correct 7 ms 8284 KB Output is correct
20 Correct 6 ms 8284 KB Output is correct
21 Correct 4 ms 8136 KB Output is correct
22 Correct 4 ms 8280 KB Output is correct
23 Correct 5 ms 8284 KB Output is correct
24 Correct 4 ms 8284 KB Output is correct
25 Correct 45 ms 10616 KB Output is correct
26 Correct 5 ms 8280 KB Output is correct
27 Correct 698 ms 9080 KB Output is correct
28 Correct 5775 ms 26452 KB Output is correct
29 Correct 6466 ms 24564 KB Output is correct
30 Correct 7100 ms 24468 KB Output is correct
31 Correct 6176 ms 28752 KB Output is correct
32 Correct 5 ms 8284 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 9096 KB Output is correct
2 Correct 174 ms 9084 KB Output is correct
3 Correct 169 ms 9052 KB Output is correct
4 Correct 169 ms 9060 KB Output is correct
5 Correct 169 ms 9048 KB Output is correct
6 Correct 14 ms 20056 KB Output is correct
7 Correct 14 ms 20060 KB Output is correct
8 Correct 14 ms 19876 KB Output is correct
9 Correct 34 ms 21416 KB Output is correct
10 Correct 9 ms 15960 KB Output is correct
11 Correct 9 ms 15964 KB Output is correct
12 Correct 44 ms 18720 KB Output is correct
13 Correct 9 ms 15964 KB Output is correct
14 Correct 9 ms 15964 KB Output is correct
15 Correct 909 ms 41012 KB Output is correct
16 Execution timed out 20039 ms 39776 KB Time limit exceeded
17 Halted 0 ms 0 KB -