Submission #786874

#	Time	Username	Problem	Language	Result	Execution time	Memory
786874		drdilyor	Wombats (IOI13_wombats)	C++17	55 / 100	20064 ms	16900 KiB

wombats

#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")

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


int r, c;
int level[5000][200];
int pass[5000][200];
int dist[200][200];

vector<char> dirty;

void update(int v2) {
    if (!dirty[v2]) return;
    dirty[v2] = 0;

    vector<int> dp(c, inf);
    dp[v2] = 0;
    for (int i = r-1; i >= 0; i--) {

        auto sum = [&](int r) {
            if (r < 0) return 0;
            return level[i][r];
        };

        vector<int> ndp(dp);

        int mn = inf;
        for (int j = 0; j < c; j++) {
            ndp[j] = min(ndp[j], mn + sum(j-1));
            mn = min(mn, dp[j] - sum(j-1));
        }

        mn = inf;
        for (int j = c-1; j >= 0; j--) {
            ndp[j] = min(ndp[j], mn - sum(j-1));
            mn = min(mn, dp[j] + sum(j-1));
        }

        for (int j = 0; j < c; j++) {
            if (i) ndp[j] += pass[i-1][j];
        }

        dp.swap(ndp);
    }
    for (int v1 = 0; v1 < c; v1++)
        dist[v1][v2] = dp[v1];
}

void init(int32_t r, int32_t c, int32_t h[5000][200], int32_t v[5000][200]) {
    ::r = r;
    ::c = c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c-1; j++) {
            level[i][j] = h[i][j];
            if (j) level[i][j] += level[i][j-1];
        }
    }

    for (int i = 0; i < r-1; i++) {
        for (int j = 0; j < c; j++) {
            pass[i][j] =v[i][j];
        }
    }
    dirty.assign(c, 1);
    memset(dist, 0, sizeof(dist));
}

void changeH(int32_t p, int32_t q, int32_t w) {
    int actual = level[p][q];
    if (q) actual -= level[p][q-1];
    int diff = w - actual;
    for (int i = q; i < c-1; i++)
        level[p][i] += diff;
    dirty.assign(c, 1);
}

void changeV(int32_t p, int32_t q, int32_t w) {
    pass[p][q] = w;
    dirty.assign(c, 1);
}

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