Submission #477265

#	Time	Username	Problem	Language	Result	Execution time	Memory
477265		tmbao	웜뱃 (IOI13_wombats)	C++14	55 / 100	20085 ms	28808 KiB

wombats

#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); dp.shrink_to_fit();
    for (int i = 0; i < columnCount; ++i) {
        dp[i].resize(columnCount, INF); dp.shrink_to_fit();
    }

    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); dp.shrink_to_fit();
    for (int i = 0; i < columnCount; ++i) {
        dp[i].resize(columnCount, 0); dp.shrink_to_fit();
        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 freeUpMemory(int i, int l, int r) {
    if (l - r < 8) {
        segTree[i * 2].clear(); segTree[i * 2].shrink_to_fit();
        segTree[i * 2 + 1].clear(); segTree[i * 2 + 1].shrink_to_fit();
    }
}

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);
    freeUpMemory(i, l, r);
}

void refresh(int i, int l, int r, int index) {
    if (r < index || index < l) {
        if (segTree[i].size() == 0) {
            initSegTree(i, l, r);
        }
        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);
    freeUpMemory(i, l, r);
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    segTree.clear();
    segTree.resize(R * 4); segTree.shrink_to_fit();
    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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24