Submission #415010

#	Time	Username	Problem	Language	Result	Execution time	Memory
415010		KoD	Wombats (IOI13_wombats)	C++17	100 / 100	6345 ms	174828 KiB

wombats

#include <bits/stdc++.h>
#include "wombats.h"

constexpr int LOG = 10;
constexpr int INF = 1000000000;
constexpr int RMAX = 5000;
constexpr int CMAX = 200;
constexpr int SEGMAX = 512;

bool chmin(int& x, const int y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

int R, C;
int hori[RMAX][CMAX], vert[RMAX][CMAX];

int size;
int dist[2 * SEGMAX][CMAX][CMAX];
int right[2 * SEGMAX];
int cumsum[CMAX];
int base[CMAX][CMAX], next[CMAX][CMAX];
int idx[CMAX][CMAX];
bool reached[2 * SEGMAX];

void setup(const int i) {
    for (int j = 0; j < C - 1; ++j) 
        cumsum[j + 1] = cumsum[j] + hori[i][j];
    for (int j = 0; j < C; ++j) 
        for (int k = 0; k < C; ++k)
            base[j][k] = std::abs(cumsum[k] - cumsum[j]);
}

void absorb(const int i, const int m) {
    for (int j = 0; j < C; ++j)
        for (int k = 0; k < C; ++k)
            next[j][k] = INF;
    for (int j = 0; j < C; ++j)
        for (int k = 0; k < C; ++k)
            if (chmin(next[j][j], dist[i][j][k] + vert[m][k] + base[k][j]))
                idx[j][j] = k;
    for (int l = 1; l < C; ++l) {
        for (int j = 0; j + l < C; ++j)
            for (int k = idx[j][j + l - 1]; k <= idx[j + 1][j + l]; ++k)
                if (chmin(next[j][j + l], dist[i][j][k] + vert[m][k] + base[k][j + l]))
                    idx[j][j + l] = k;
        for (int j = l; j < C; ++j)
            for (int k = idx[j - 1][j - l]; k <= idx[j][j - l + 1]; ++k)
                if (chmin(next[j][j - l], dist[i][j][k] + vert[m][k] + base[k][j - l]))
                    idx[j][j - l] = k;
    }
    std::memcpy(dist[i], next, sizeof(dist[i]));
}

void fetch(const int k) {
    if (reached[2 * k]) {
        reached[k] = true;
        std::memcpy(dist[k], dist[2 * k], sizeof(dist[k]));
        right[k] = right[2 * k];
        if (reached[2 * k + 1]) {
            std::memcpy(base, dist[2 * k + 1], sizeof(base));
            absorb(k, right[k]);
            right[k] = right[2 * k + 1];
        }
    }
}

void update(int k) {
    k += SEGMAX;
    while (k > 1) {
        k >>= 1;
        fetch(k);
    }
}

void recalc(const int i) {
    const int up = LOG * i;
    const int down = std::min(up + LOG, R);
    setup(up);
    std::memcpy(dist[SEGMAX + i], base, sizeof(dist[SEGMAX + i]));
    right[SEGMAX + i] = down - 1;
    for (int j = up + 1; j < down; ++j) {
        setup(j);
        absorb(SEGMAX + i, j - 1);
    }
}

void init(int N, int M, int H[RMAX][CMAX], int V[RMAX][CMAX]) {
    R = N, C = M;
    for (int i = 0; i < R; ++i) 
        for (int j = 0; j < C - 1; ++j) 
            hori[i][j] = H[i][j];
    for (int i = 0; i < R - 1; ++i) 
        for (int j = 0; j < C; ++j) 
            vert[i][j] = V[i][j];
    size = (R + LOG - 1) / LOG;
    for (int i = 0; i < size; ++i) {
        recalc(i);
        reached[SEGMAX + i] = true;
    }
    for (int i = SEGMAX - 1; i > 0; --i) {
        fetch(i);
    }
}

void changeH(int P, int Q, int W) {
    hori[P][Q] = W;
    recalc(P / LOG);
    update(P / LOG);
}

void changeV(int P, int Q, int W) {
    vert[P][Q] = W;
    recalc(P / LOG);
    update(P / LOG);
}

int escape(int V1, int V2) {
    return dist[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: 21 / 21
• Subtask 6: 24 / 24