oj.uz

Submission #1067811

# Submission time Handle Problem Language Result Execution time Memory
1067811 2024-08-21T03:38:42 Z Plurm Wombats (IOI13_wombats) C++11
55 / 100
 20000 ms 33732 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);
            for (int nc = 0; nc < C; nc++) {
                for (int oc = 0; oc < C; oc++) {
                    dpnw[nc] = min(dpnw[nc], dpst[oc] + qsr[row][max(nc, oc)] -
                                                 qsr[row][min(nc, oc)] +
                                                 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;
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);
            for (int nc = 0; nc < C; nc++) {
                for (int oc = 0; oc < C; oc++) {
                    dpnw[nc] = min(dpnw[nc], dpst[oc] + blans[blk].ans[oc][nc]);
                }
            }
            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 8 ms 15964 KB Output is correct
2 Correct 9 ms 15964 KB Output is correct
3 Correct 51 ms 18944 KB Output is correct
4 Correct 9 ms 15960 KB Output is correct
5 Correct 8 ms 15964 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct
7 Correct 4 ms 8280 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 8284 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 4 ms 8240 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 8280 KB Output is correct
8 Correct 5 ms 8284 KB Output is correct
9 Correct 5 ms 8228 KB Output is correct
10 Correct 4 ms 8284 KB Output is correct
11 Correct 42 ms 10632 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 2362 ms 8928 KB Output is correct
2 Correct 2431 ms 9044 KB Output is correct
3 Correct 2449 ms 8920 KB Output is correct
4 Correct 2424 ms 9068 KB Output is correct
5 Correct 2469 ms 9052 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 11500 ms 9060 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 13 ms 20060 KB Output is correct
2 Correct 17 ms 20084 KB Output is correct
3 Correct 17 ms 19916 KB Output is correct
4 Correct 36 ms 21332 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2375 ms 9096 KB Output is correct
2 Correct 2301 ms 9040 KB Output is correct
3 Correct 2506 ms 9044 KB Output is correct
4 Correct 2475 ms 9044 KB Output is correct
5 Correct 2392 ms 9296 KB Output is correct
6 Correct 14 ms 20060 KB Output is correct
7 Correct 12 ms 19912 KB Output is correct
8 Correct 12 ms 19964 KB Output is correct
9 Correct 34 ms 21368 KB Output is correct
10 Correct 8 ms 15964 KB Output is correct
11 Correct 11 ms 15964 KB Output is correct
12 Correct 48 ms 18716 KB Output is correct
13 Correct 10 ms 15964 KB Output is correct
14 Correct 9 ms 16144 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 8136 KB Output is correct
18 Correct 5 ms 8280 KB Output is correct
19 Correct 5 ms 8284 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 8280 KB Output is correct
23 Correct 5 ms 8320 KB Output is correct
24 Correct 4 ms 8284 KB Output is correct
25 Correct 45 ms 10584 KB Output is correct
26 Correct 5 ms 8284 KB Output is correct
27 Correct 11772 ms 9060 KB Output is correct
28 Execution timed out 20060 ms 26804 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2378 ms 9092 KB Output is correct
2 Correct 2382 ms 9080 KB Output is correct
3 Correct 2420 ms 8900 KB Output is correct
4 Correct 2460 ms 9228 KB Output is correct
5 Correct 2344 ms 9056 KB Output is correct
6 Correct 13 ms 20060 KB Output is correct
7 Correct 12 ms 20060 KB Output is correct
8 Correct 12 ms 20084 KB Output is correct
9 Correct 33 ms 21292 KB Output is correct
10 Correct 8 ms 15964 KB Output is correct
11 Correct 8 ms 16012 KB Output is correct
12 Correct 44 ms 18700 KB Output is correct
13 Correct 9 ms 15964 KB Output is correct
14 Correct 9 ms 16088 KB Output is correct
15 Execution timed out 20055 ms 33732 KB Time limit exceeded
16 Halted 0 ms 0 KB -