oj.uz

Submission #477259

# Submission time Handle Problem Language Result Execution time Memory
477259 2021-10-01T13:11:05 Z tmbao Wombats (IOI13_wombats) C++14
55 / 100
 586 ms 262148 KB 
#include "wombats.h"

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 10;

vector<vector<int>> mergeDp(
    const vector<vector<int>>& dp1, const vector<vector<int>>& dp2, int* vertical, int columnCount) {
    vector<vector<int>> dp;
    dp.resize(columnCount);
    for (int i = 0; i < columnCount; ++i) {
        dp[i].resize(columnCount, INF);
    }

    vector<int> optimal;
    optimal.resize(columnCount + 1, 0);
    optimal[columnCount] = columnCount - 1;

    for (int i = 0; i < columnCount; ++i) {
        for (int j = columnCount - 1; j >= 0; --j) {
            for (int k = optimal[j]; k <= optimal[j + 1]; ++k) {
                if (dp[i][j] >= dp1[i][k] + vertical[k] + dp2[k][j]) {
                    dp[i][j] = dp1[i][k] + vertical[k] + dp2[k][j];
                    optimal[j] = k;
                }
            }
        }
    }

    return dp;
}

vector<vector<int>> initDp(int* horizontal, int columnCount) {
    vector<vector<int>> dp;
    dp.resize(columnCount);
    for (int i = 0; i < columnCount; ++i) {
        dp[i].resize(columnCount, 0);
        for (int j = i; j + 1 < columnCount; ++j) {
            dp[i][j + 1] = dp[i][j] + horizontal[j];
        }
        for (int j = i - 1; j >= 0; --j) {
            dp[i][j] = dp[i][j + 1] + horizontal[j];
        }
    }
    return dp;
}

int rowCount, columnCount;
int horizontal[5000][200];
int vertical[5000][200];
vector<vector<vector<int>>> segTree;

void initSegTree(int i, int l, int r) {
    if (l == r) {
        segTree[i] = initDp(horizontal[l], columnCount);
        return;
    }
    int mid = (l + r) / 2;
    initSegTree(i * 2, l, mid);
    initSegTree(i * 2 + 1, mid + 1, r);
    segTree[i] = mergeDp(segTree[i * 2], segTree[i * 2 + 1], vertical[mid], columnCount);
}

void refresh(int i, int l, int r, int index) {
    if (r < index || index < l) {
        return;
    }
    if (l == r) {
        segTree[i].clear();
        segTree[i] = initDp(horizontal[l], columnCount);
        return;
    }
    int mid = (l + r) / 2;
    refresh(i * 2, l, mid, index);
    refresh(i * 2 + 1, mid + 1, r, index);
    segTree[i].clear();
    segTree[i] = mergeDp(segTree[i * 2], segTree[i * 2 + 1], vertical[mid], columnCount);
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    segTree.clear();
    segTree.resize(R * 4);
    rowCount = R;
    columnCount = C; 
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j + 1 < C; ++j) {
            horizontal[i][j] = H[i][j];
        }
    }
    for (int i = 0; i + 1 < R; ++i) {
        for (int j = 0; j < C; ++j) {
            vertical[i][j] = V[i][j];
        }
    }
    initSegTree(1, 0, rowCount - 1);
}

void changeH(int P, int Q, int W) {
    horizontal[P][Q] = W;
    refresh(1, 0, rowCount - 1, P);
}

void changeV(int P, int Q, int W) {
    vertical[P][Q] = W;
    refresh(1, 0, rowCount - 1, P);
}

int escape(int V1, int V2) {
    return segTree[1][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 7 ms 9164 KB Output is correct
2 Correct 8 ms 9144 KB Output is correct
3 Correct 83 ms 11004 KB Output is correct
4 Correct 7 ms 9164 KB Output is correct
5 Correct 7 ms 9164 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 75 ms 1416 KB Output is correct
12 Correct 1 ms 460 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 9236 KB Output is correct
2 Correct 76 ms 8908 KB Output is correct
3 Correct 98 ms 9196 KB Output is correct
4 Correct 99 ms 9164 KB Output is correct
5 Correct 96 ms 9128 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 317 ms 9192 KB Output is correct
10 Correct 0 ms 204 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17612 KB Output is correct
2 Correct 13 ms 17612 KB Output is correct
3 Correct 13 ms 17568 KB Output is correct
4 Correct 61 ms 18404 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 9036 KB Output is correct
2 Correct 73 ms 9036 KB Output is correct
3 Correct 98 ms 9196 KB Output is correct
4 Correct 99 ms 9200 KB Output is correct
5 Correct 102 ms 9032 KB Output is correct
6 Correct 12 ms 17596 KB Output is correct
7 Correct 12 ms 17612 KB Output is correct
8 Correct 12 ms 17612 KB Output is correct
9 Correct 54 ms 18460 KB Output is correct
10 Correct 6 ms 9164 KB Output is correct
11 Correct 7 ms 9196 KB Output is correct
12 Correct 84 ms 10820 KB Output is correct
13 Correct 7 ms 9164 KB Output is correct
14 Correct 7 ms 9164 KB Output is correct
15 Correct 1 ms 220 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 78 ms 1348 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 317 ms 9208 KB Output is correct
28 Runtime error 507 ms 262148 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 9104 KB Output is correct
2 Correct 75 ms 8996 KB Output is correct
3 Correct 95 ms 9200 KB Output is correct
4 Correct 96 ms 9192 KB Output is correct
5 Correct 94 ms 9108 KB Output is correct
6 Correct 13 ms 17612 KB Output is correct
7 Correct 12 ms 17672 KB Output is correct
8 Correct 13 ms 17568 KB Output is correct
9 Correct 52 ms 18460 KB Output is correct
10 Correct 7 ms 9192 KB Output is correct
11 Correct 7 ms 9164 KB Output is correct
12 Correct 83 ms 10804 KB Output is correct
13 Correct 8 ms 9164 KB Output is correct
14 Correct 7 ms 9164 KB Output is correct
15 Runtime error 586 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -