oj.uz

Submission #53012

# Submission time Handle Problem Language Result Execution time Memory
53012 2018-06-27T16:56:22 Z imeimi2000 Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 121492 KB 
#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 init(int s, int e) {
        int sum[200] = {};
        for (int i = 0; i < c; ++i) {
            for (int j = 0; j < c; ++j) {
                tp[i][j] = inf;
            }
            tp[i][i] = 0;
        }
        for (int i = s; i < e; ++i) {
            for (int j = 0; j < c; ++j) {
                if (j) sum[j] = sum[j - 1] + h[i][j - 1];
                for (int k = 0; k < c; ++k) {
                    to[j][k] = tp[j][k];
                }
            }
            for (int j = 0; j < c; ++j) {
                for (int k = 0; k < c; ++k) {
                    tp[j][k] = inf;
                    for (int l = 0; l < c; ++l) {
                        tp[j][k] = imin(tp[j][k], to[j][l] + iabs(sum[l] - sum[k]));
                    }
                    tp[j][k] += v[i][k];
                }
            }
        }
        for (int i = 1; i < c; ++i) {
            sum[i] = sum[i - 1] + h[e][i - 1];
        }
        for (int i = 0; i < c; ++i) {
            for (int j = 0; j < c; ++j) {
                to[i][j] = inf;
                for (int k = 0; k < c; ++k) {
                    to[i][j] = imin(to[i][j], tp[i][k] + iabs(sum[k] - sum[j]));
                }
            }
        }
    }
    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;
                    }
                }
            }
        }
    }
} 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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10616 KB Output is correct
2 Correct 11 ms 10756 KB Output is correct
3 Correct 83 ms 13560 KB Output is correct
4 Correct 11 ms 13560 KB Output is correct
5 Correct 13 ms 13560 KB Output is correct
6 Correct 3 ms 13560 KB Output is correct
7 Correct 2 ms 13560 KB Output is correct
8 Correct 2 ms 13560 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13560 KB Output is correct
2 Correct 2 ms 13560 KB Output is correct
3 Correct 2 ms 13560 KB Output is correct
4 Correct 4 ms 13560 KB Output is correct
5 Correct 3 ms 13560 KB Output is correct
6 Correct 3 ms 13560 KB Output is correct
7 Correct 3 ms 13560 KB Output is correct
8 Correct 3 ms 13560 KB Output is correct
9 Correct 3 ms 13560 KB Output is correct
10 Correct 4 ms 13560 KB Output is correct
11 Correct 106 ms 13560 KB Output is correct
12 Correct 4 ms 13560 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 20164 KB Output is correct
2 Correct 536 ms 20164 KB Output is correct
3 Correct 582 ms 20492 KB Output is correct
4 Correct 590 ms 20556 KB Output is correct
5 Correct 495 ms 20556 KB Output is correct
6 Correct 2 ms 20556 KB Output is correct
7 Correct 2 ms 20556 KB Output is correct
8 Correct 2 ms 20556 KB Output is correct
9 Correct 1573 ms 20728 KB Output is correct
10 Correct 2 ms 20728 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 20956 KB Output is correct
2 Correct 22 ms 21028 KB Output is correct
3 Correct 18 ms 21084 KB Output is correct
4 Correct 70 ms 22468 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 22468 KB Output is correct
2 Correct 514 ms 22468 KB Output is correct
3 Correct 519 ms 22468 KB Output is correct
4 Correct 546 ms 22468 KB Output is correct
5 Correct 485 ms 22468 KB Output is correct
6 Correct 17 ms 22468 KB Output is correct
7 Correct 21 ms 22468 KB Output is correct
8 Correct 18 ms 22468 KB Output is correct
9 Correct 61 ms 23752 KB Output is correct
10 Correct 12 ms 23752 KB Output is correct
11 Correct 10 ms 23752 KB Output is correct
12 Correct 85 ms 23752 KB Output is correct
13 Correct 11 ms 23752 KB Output is correct
14 Correct 10 ms 23752 KB Output is correct
15 Correct 2 ms 23752 KB Output is correct
16 Correct 2 ms 23752 KB Output is correct
17 Correct 2 ms 23752 KB Output is correct
18 Correct 4 ms 23752 KB Output is correct
19 Correct 4 ms 23752 KB Output is correct
20 Correct 3 ms 23752 KB Output is correct
21 Correct 5 ms 23752 KB Output is correct
22 Correct 4 ms 23752 KB Output is correct
23 Correct 4 ms 23752 KB Output is correct
24 Correct 4 ms 23752 KB Output is correct
25 Correct 125 ms 23752 KB Output is correct
26 Correct 5 ms 23752 KB Output is correct
27 Correct 1626 ms 25692 KB Output is correct
28 Correct 19817 ms 109212 KB Output is correct
29 Correct 15366 ms 110520 KB Output is correct
30 Correct 15645 ms 114116 KB Output is correct
31 Correct 19016 ms 121492 KB Output is correct
32 Correct 2 ms 121492 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 121492 KB Output is correct
2 Correct 469 ms 121492 KB Output is correct
3 Correct 503 ms 121492 KB Output is correct
4 Correct 489 ms 121492 KB Output is correct
5 Correct 538 ms 121492 KB Output is correct
6 Correct 17 ms 121492 KB Output is correct
7 Correct 17 ms 121492 KB Output is correct
8 Correct 16 ms 121492 KB Output is correct
9 Correct 53 ms 121492 KB Output is correct
10 Correct 10 ms 121492 KB Output is correct
11 Correct 10 ms 121492 KB Output is correct
12 Correct 108 ms 121492 KB Output is correct
13 Correct 11 ms 121492 KB Output is correct
14 Correct 11 ms 121492 KB Output is correct
15 Execution timed out 20023 ms 121492 KB Time limit exceeded
16 Halted 0 ms 0 KB -