oj.uz

Submission #1067819

# Submission time Handle Problem Language Result Execution time Memory
1067819 2024-08-21T03:56:31 Z Plurm Wombats (IOI13_wombats) C++11
18 / 100
 158 ms 21332 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 * 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 8540 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 9048 KB Output is correct
2 Correct 123 ms 8796 KB Output is correct
3 Correct 158 ms 8740 KB Output is correct
4 Correct 123 ms 8804 KB Output is correct
5 Correct 123 ms 8800 KB Output is correct
6 Runtime error 2 ms 348 KB Execution killed with signal 8
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19896 KB Output is correct
2 Correct 13 ms 20060 KB Output is correct
3 Correct 21 ms 19988 KB Output is correct
4 Correct 34 ms 21332 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 8808 KB Output is correct
2 Correct 124 ms 8796 KB Output is correct
3 Correct 125 ms 8796 KB Output is correct
4 Correct 134 ms 8804 KB Output is correct
5 Correct 125 ms 8792 KB Output is correct
6 Correct 13 ms 20100 KB Output is correct
7 Correct 20 ms 20068 KB Output is correct
8 Correct 13 ms 20060 KB Output is correct
9 Correct 37 ms 21324 KB Output is correct
10 Runtime error 5 ms 8284 KB Execution killed with signal 8
11 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 8708 KB Output is correct
2 Correct 118 ms 8796 KB Output is correct
3 Correct 151 ms 8800 KB Output is correct
4 Correct 138 ms 8800 KB Output is correct
5 Correct 124 ms 8796 KB Output is correct
6 Correct 16 ms 20056 KB Output is correct
7 Correct 14 ms 20060 KB Output is correct
8 Correct 14 ms 20060 KB Output is correct
9 Correct 37 ms 21220 KB Output is correct
10 Runtime error 5 ms 8284 KB Execution killed with signal 8
11 Halted 0 ms 0 KB -