Submission #477242

#	Time	Username	Problem	Language	Result	Execution time	Memory
477242		tmbao	웜뱃 (IOI13_wombats)	C++14	Compilation error	0 ms	0 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);
    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]) {
                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, rowCount, columnCount);
    initSegTree(i * 2 + 1, mid + 1, r, rowCount, columnCount);
    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] == 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;
    horizontal = H;
    vertical = V;
    initSegTree(1, 0, rowCount);
}

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

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

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;
      |      ^~~
wombats.cpp: In function 'std::vector<std::vector<int> > mergeDp(const std::vector<std::vector<int> >&, const std::vector<std::vector<int> >&, int*, int)':
wombats.cpp:23:57: error: expected ';' before ')' token
   23 |             for (int k = optimal[j]; k <= optimal[j + 1]) {
      |                                                         ^
      |                                                         ;
wombats.cpp: In function 'void initSegTree(int, int, int)':
wombats.cpp:62:53: error: too many arguments to function 'void initSegTree(int, int, int)'
   62 |     initSegTree(i * 2, l, mid, rowCount, columnCount);
      |                                                     ^
wombats.cpp:55:6: note: declared here
   55 | void initSegTree(
      |      ^~~~~~~~~~~
wombats.cpp:63:61: error: too many arguments to function 'void initSegTree(int, int, int)'
   63 |     initSegTree(i * 2 + 1, mid + 1, r, rowCount, columnCount);
      |                                                             ^
wombats.cpp:55:6: note: declared here
   55 | void initSegTree(
      |      ^~~~~~~~~~~
wombats.cpp: In function 'void init(int, int, int (*)[200], int (*)[200])':
wombats.cpp:86:16: error: incompatible types in assignment of 'int (*)[200]' to 'int [5000][200]'
   86 |     horizontal = H;
      |     ~~~~~~~~~~~^~~
wombats.cpp:87:14: error: incompatible types in assignment of 'int (*)[200]' to 'int [5000][200]'
   87 |     vertical = V;
      |     ~~~~~~~~~^~~
wombats.cpp: In function 'void changeH(int, int, int)':
wombats.cpp:93:27: error: too few arguments to function 'void refresh(int, int, int, int)'
   93 |     refresh(1, 0, rowCount);
      |                           ^
wombats.cpp:67:6: note: declared here
   67 | void refresh(int i, int l, int r, int index) {
      |      ^~~~~~~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:98:27: error: too few arguments to function 'void refresh(int, int, int, int)'
   98 |     refresh(1, 0, rowCount);
      |                           ^
wombats.cpp:67:6: note: declared here
   67 | void refresh(int i, int l, int r, int index) {
      |      ^~~~~~~