Submission #786571

#	Time	Username	Problem	Language	Result	Execution time	Memory
786571		drdilyor	Wombats (IOI13_wombats)	C++17	39 / 100	20073 ms	16268 KiB

wombats

#include<bits/stdc++.h>
#include "wombats.h"
using namespace std;
const int inf = 1e9;
using ll = long long;
constexpr ll infl = 1e18;

int sum = 0;
int r, c;
vector<vector<int>> level;
vector<vector<int>> pass;
vector<vector<ll>> dist;

void init(int r, int c, int h[5000][200], int v[5000][200]) {
    assert(c<= 2 || (r <= 100 && c <= 100));
    ::r = r;
    ::c = c;
    level.resize(r);
    for (int i = 0; i < r; i++) {
        level[i].resize(c-1);
        for (int j = 0; j < c-1; j++) {
            level[i][j] = h[i][j];
        }
    }

    pass.resize(r-1);
    for (int i = 0; i < r-1; i++) {
        pass[i].resize(c);
        for (int j = 0; j < c; j++) {
            pass[i][j] = v[i][j];
        }
    }

    dist = vector(c, vector(c, 0ll));
    for (int v2 = 0; v2 < c; v2++) {
        vector<ll> dp(c, infl);
        dp[v2] = 0;
        for (int i = r-1; i >= 0; i--) {
            vector<ll> ndp(c, infl);
            for (int j = 0; j < c; j++) {
                for (ll k = j - 1, sum = 0; k >= 0; k--) {
                    sum += level[i][k];
                    ndp[j] = min(ndp[j], dp[k] + sum);
                }
                for (ll k = j, sum = 0; k < c; k++) {
                    ndp[j] = min(ndp[j], dp[k] + sum);
                    if (k < c-1) sum += level[i][k];
                }
                if (i) ndp[j] += pass[i-1][j];
            }
            dp.swap(ndp);
        }
        for (int v1 = 0; v1 < c; v1++)
            dist[v1][v2] = dp[v1];
    }
}

void changeH(int p, int q, int w) {
    level[p][q] = w;

    for (int v2 = 0; v2 < c; v2++) {
        vector<ll> dp(c, infl);
        dp[v2] = 0;
        for (int i = r-1; i >= 0; i--) {
            vector<ll> ndp(c, infl);
            for (int j = 0; j < c; j++) {
                for (ll k = j - 1, sum = 0; k >= 0; k--) {
                    sum += level[i][k];
                    ndp[j] = min(ndp[j], dp[k] + sum);
                }
                for (ll k = j, sum = 0; k < c; k++) {
                    ndp[j] = min(ndp[j], dp[k] + sum);
                    if (k < c-1) sum += level[i][k];
                }
                if (i) ndp[j] += pass[i-1][j];
            }
            dp.swap(ndp);
        }
        for (int v1 = 0; v1 < c; v1++)
            dist[v1][v2] = dp[v1];
    }
}

void changeV(int p, int q, int w) {
    pass[p][q] = w;

    for (int v2 = 0; v2 < c; v2++) {
        vector<ll> dp(c, infl);
        dp[v2] = 0;
        for (int i = r-1; i >= 0; i--) {
            vector<ll> ndp(c, infl);
            for (int j = 0; j < c; j++) {
                for (ll k = j - 1, sum = 0; k >= 0; k--) {
                    sum += level[i][k];
                    ndp[j] = min(ndp[j], dp[k] + sum);
                }
                for (ll k = j, sum = 0; k < c; k++) {
                    ndp[j] = min(ndp[j], dp[k] + sum);
                    if (k < c-1) sum += level[i][k];
                }
                if (i) ndp[j] += pass[i-1][j];
            }
            dp.swap(ndp);
        }
        for (int v1 = 0; v1 < c; v1++)
            dist[v1][v2] = dp[v1];
    }
}

int escape(int v1, int v2) {
    return dist[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: 0 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24