Submission #53013

#	Time	Username	Problem	Language	Result	Execution time	Memory
53013		imeimi2000	Wombats (IOI13_wombats)	C++17	100 / 100	11152 ms	242548 KiB

wombats

#include "wombats.h"

int r, c;
const int inf = 1e8;
short h[5000][200];
short v[5000][200];

int iabs(int x) {
    return x < 0 ? -x : x;
}

int imin(int x, int y) {
    return x < y ? x : y;
}

int tp[200][200];
struct node {
    int to[200][200];
    void add(const node &l, const node &r, int m) {
        for (int i = 0; i < c; ++i) {
            to[i][i] = inf;
            for (int j = 0; j < c; ++j) {
                int x = l.to[i][j] + r.to[j][i] + v[m][j];
                if (x < to[i][i]) {
                    tp[i][i] = j;
                    to[i][i] = x;
                }
            }
        }
        for (int i = 1 - c; i < c; ++i) {
            for (int j = 0; j < c; ++j) {
                if (j + i < 0 || c <= j + i) continue;
                to[j][j + i] = inf;
                int s = j + i > 0 ? tp[j][j + i - 1] : 0;
                int e = j + 1 < c ? tp[j + 1][j + i] : c - 1;
                for (int k = s; k <= e; ++k) {
                    int x = l.to[j][k] + r.to[k][j + i] + v[m][k];
                    if (x < to[j][j + i]) {
                        tp[j][j + i] = k;
                        to[j][j + i] = x;
                    }
                }
            }
        }
    }
    void fill(int x) {
        int sum[200] = {};
        for (int i = 1; i < c; ++i) {
            sum[i] = sum[i - 1] + h[x][i - 1];
        }
        for (int i = 0; i < c; ++i) {
            for (int j = 0; j < c; ++j) {
                to[i][j] = iabs(sum[i] - sum[j]);
            }
        }
    }
    void init(int s, int e) {
        node t1, t2;
        fill(s);
        for (int i = s + 1; i <= e; ++i) {
            t1 = *this;
            t2.fill(i);
            add(t1, t2, i - 1);
        }
    }
} seg[1 << 10];

void initSeg(int i, int s, int e) {
    if (s == e || (1 << 10) <= (i << 1 | 1)) {
        seg[i].init(s, e);
        return;
    }
    int m = (s + e) / 2;
    initSeg(i << 1, s, m);
    initSeg(i << 1 | 1, m + 1, e);
    seg[i].add(seg[i << 1], seg[i << 1 | 1], m);
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r = R;
    c = C;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (j + 1 < c) h[i][j] = H[i][j];
            if (i + 1 < r) v[i][j] = V[i][j];
        }
    }
    initSeg(1, 0, r - 1);
}

void update(int i, int s, int e, int x) {
    if (s == e || (1 << 10) <= (i << 1 | 1)) {
        seg[i].init(s, e);
        return;
    }
    int m = (s + e) / 2;
    if (x <= m) update(i << 1, s, m, x);
    else update(i << 1 | 1, m + 1, e, x);
    seg[i].add(seg[i << 1], seg[i << 1 | 1], m);
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    update(1, 0, r - 1, P);
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    update(1, 0, r - 1, P);
}

int escape(int V1, int V2) {
    return seg[1].to[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]
  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