Submission #603839

#	Time	Username	Problem	Language	Result	Execution time	Memory
603839		KoD	Wombats (IOI13_wombats)	C++17	100 / 100	3026 ms	176044 KiB

wombats

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include "wombats.h"
#include <bits/stdc++.h>

using std::array;

constexpr int INF = (1 << 30) - 1;
const int MAX_R = 5000;
const int MAX_C = 200;
const int BLOCK = 10;
const int SEG = 512;

template <class T>
bool setmin(T& x, const T& y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

// grid data
int R, C;
int H[MAX_R][MAX_C];
int V[MAX_R][MAX_C];

// segtree data
array<array<int, MAX_C>, MAX_C> dist[2 * SEG];
int append[2 * SEG];

void calc_group(const int g) {
    const int i0 = BLOCK * g;
    const int i1 = std::min(R, i0 + BLOCK);
    static array<int, MAX_C> accum = {};
    static array<int, MAX_C> next = {};
    const auto setup = [&](const int i) {
        for (int j = 0; j < C - 1; ++j)
            accum[j + 1] = accum[j] + H[i][j];
    };
    setup(i0);
    auto& dp = dist[SEG + g];
    for (int a = 0; a < C; ++a)
        for (int b = a; b < C; ++b)
            dp[a][b] = dp[b][a] = accum[b] - accum[a];
    for (int i = i0; i < i1 - 1; ++i) {
        setup(i + 1);
        for (int a = 0; a < C; ++a) {
            next.fill(INF);
            for (int b = 0, min = INF; b < C; ++b) {
                setmin(min, dp[a][b] + V[i][b] - accum[b]);
                setmin(next[b], min + accum[b]);
            }
            for (int b = C - 1, min = INF; b >= 0; --b) {
                setmin(min, dp[a][b] + V[i][b] + accum[b]);
                setmin(next[b], min - accum[b]);
            }
            dp[a] = next;
        }
    }
}

void fetch(const int g) {
    const int l = 2 * g;
    const int r = 2 * g + 1;
    append[g] = append[r];
    if (append[l] == R - 1) {
        dist[g] = dist[l];
        return;
    }
    auto& dp = dist[g];
    for (int a = 0; a < C; ++a)
        for (int b = 0; b < C; ++b)
            dp[a][b] = INF;
    static array<array<int, MAX_C>, MAX_C> best = {};
    const auto check = [&](const int a, const int c, const int b) {
        if (setmin(dp[a][b], dist[l][a][c] + V[append[l]][c] + dist[r][c][b]))
            best[a][b] = c;
    };
    for (int a = 0; a < C; ++a)
        for (int b = 0; b < C; ++b)
            check(a, b, a);
    for (int len = 1; len < C; ++len) {
        for (int a = 0; a + len < C; ++a)
            for (int b = best[a][a + len - 1]; b <= best[a + 1][a + len]; ++b)
                check(a, b, a + len);
        for (int a = len; a < C; ++a)
            for (int b = best[a - 1][a - len]; b <= best[a][a - len + 1]; ++b)
                check(a, b, a - len);
    }
}

void init(int r, int c, int h[MAX_R][MAX_C], int v[MAX_R][MAX_C]) {
    R = r, C = c;
    std::memcpy(H, h, sizeof(H));
    std::memcpy(V, v, sizeof(V));
    const int n = (R + BLOCK - 1) / BLOCK;
    for (int g = 0; g < n; ++g)
        calc_group(g);
    for (int g = 0; g < SEG; ++g)
        append[SEG + g] = std::min(BLOCK * (g + 1) - 1, R - 1);
    for (int g = SEG - 1; g > 0; --g)
        fetch(g);
}

void changeH(int p, int q, int w) {
    H[p][q] = w;
    const int g = p / BLOCK;
    calc_group(g);
    for (int k = SEG + g; (k >>= 1) > 0;)
        fetch(k);
}

void changeV(int p, int q, int w) {
    V[p][q] = w;
    const int g = p / BLOCK;
    calc_group(g);
    for (int k = SEG + g; (k >>= 1) > 0;)
        fetch(k);
}

int escape(int v0, int v1) {
    return dist[1][v0][v1];
}

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: 21 / 21
• Subtask 6: 24 / 24