oj.uz

Submission #477253

# Submission time Handle Problem Language Result Execution time Memory
477253 2021-10-01T12:23:52 Z tmbao Wombats (IOI13_wombats) C++14
55 / 100
 670 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.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 8 ms 9164 KB Output is correct
2 Correct 7 ms 9164 KB Output is correct
3 Correct 99 ms 10744 KB Output is correct
4 Correct 7 ms 9164 KB Output is correct
5 Correct 8 ms 9164 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

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 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 71 ms 1344 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 94 ms 9112 KB Output is correct
2 Correct 75 ms 9040 KB Output is correct
3 Correct 101 ms 9224 KB Output is correct
4 Correct 97 ms 9396 KB Output is correct
5 Correct 93 ms 9192 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 315 ms 9264 KB Output is correct
10 Correct 1 ms 208 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17612 KB Output is correct
2 Correct 15 ms 17680 KB Output is correct
3 Correct 17 ms 17716 KB Output is correct
4 Correct 69 ms 19020 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 9036 KB Output is correct
2 Correct 77 ms 9040 KB Output is correct
3 Correct 100 ms 9272 KB Output is correct
4 Correct 107 ms 9284 KB Output is correct
5 Correct 96 ms 9200 KB Output is correct
6 Correct 13 ms 17744 KB Output is correct
7 Correct 13 ms 17728 KB Output is correct
8 Correct 12 ms 17744 KB Output is correct
9 Correct 59 ms 19108 KB Output is correct
10 Correct 10 ms 9168 KB Output is correct
11 Correct 7 ms 9168 KB Output is correct
12 Correct 86 ms 12016 KB Output is correct
13 Correct 7 ms 9168 KB Output is correct
14 Correct 7 ms 9168 KB Output is correct
15 Correct 1 ms 208 KB Output is correct
16 Correct 0 ms 208 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 1 ms 464 KB Output is correct
21 Correct 1 ms 464 KB Output is correct
22 Correct 1 ms 464 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 464 KB Output is correct
25 Correct 78 ms 2760 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 316 ms 9288 KB Output is correct
28 Runtime error 525 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 96 ms 9036 KB Output is correct
2 Correct 77 ms 9088 KB Output is correct
3 Correct 99 ms 9280 KB Output is correct
4 Correct 97 ms 9296 KB Output is correct
5 Correct 95 ms 9188 KB Output is correct
6 Correct 16 ms 17744 KB Output is correct
7 Correct 17 ms 17716 KB Output is correct
8 Correct 13 ms 17744 KB Output is correct
9 Correct 61 ms 19036 KB Output is correct
10 Correct 7 ms 9168 KB Output is correct
11 Correct 7 ms 9168 KB Output is correct
12 Correct 82 ms 12012 KB Output is correct
13 Correct 7 ms 9232 KB Output is correct
14 Correct 7 ms 9264 KB Output is correct
15 Runtime error 670 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -