oj.uz

Submission #159746

# Submission time Handle Problem Language Result Execution time Memory
159746 2019-10-24T12:21:45 Z PeppaPig Wombats (IOI13_wombats) C++14
100 / 100
 5866 ms 199092 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 5e3+5;
const int M = 205;

int n, m;
int H[N][M], V[N][M], opt[M][M];

struct item {
    int dp[M][M];

    item() {}

    int* operator[](int x) { return dp[x]; }

    const int* operator[](int x) const { return dp[x]; };

    friend item operator+(const item &a, const item &b) {
        item ret;
        fill_n(ret.dp[0], M*M, INT_MAX);
        for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) if(ret[0][i] > a[0][j] + b[j][i]) {
            ret[0][i] = a[0][j] + b[j][i];
            opt[0][i] = j;
        }
        //Paths don't cross, or else you can replace both paths with the minimum one
        //opt[i-1][j] <= opt[i][j] <= opt[i][j+1];
        for(int i = 1; i < m; i++) {
            opt[i][m] = m - 1;
            for(int j = m-1; ~j; j--) for(int k = opt[i-1][j]; k <= opt[i][j+1]; k++) if(ret[i][j] > a[i][k] + b[k][j]) {
                ret[i][j] = a[i][k] + b[k][j];
                opt[i][j] = k;
            }
        }
        return ret;
    }
} t[1 << 10], tmp[10];

void newleaf(int p, int l, int r) {
    for(int k = l; k <= r; k++) for(int i = 0; i < m; i++) for(int j = 0; j < m; j++)
        tmp[k - l][i][j] = V[k][j] + abs(H[k][j] - H[k][i]);
    t[p] = tmp[0];
    for(int i = 1; i < r - l + 1; i++) t[p] = t[p] + tmp[i];
}

void build(int p = 1, int l = 0, int r = n-1) {
    if(r - l + 1 <= 10) return void(newleaf(p, l, r));
    int mid = (l + r) >> 1;
    build(p<<1, l, mid), build(p<<1|1, mid+1, r);
    t[p] = t[p<<1] + t[p<<1|1];
}

void update(int x, int p = 1, int l = 0, int r = n-1) {
    if(r - l + 1 <= 10) return void(newleaf(p, l, r));
    int mid = (l + r) >> 1;
    if(x <= mid) update(x, p<<1, l, mid);
    else update(x, p<<1|1, mid+1, r);
    t[p] = t[p<<1] + t[p<<1|1];
}

void init(int R, int C, int _H[5000][200], int _V[5000][200]) {
    n = R, m = C;
    for(int i = 0; i < n; i++) for(int j = 0; j < m-1; j++)
        H[i][j + 1] = _H[i][j] + H[i][j];
    for(int i = 0; i < n-1; i++) for(int j = 0; j < m; j++)
        V[i][j] = _V[i][j];
    build();
}

void changeH(int P, int Q, int W) {
    int d = W - (H[P][Q + 1] - H[P][Q]);
    for(int i = Q + 1; i < m; i++) H[P][i] += d;
    update(P);
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    update(P);
}

int escape(int V1, int V2) {
    return t[1][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 686 ms 178552 KB Output is correct
2 Correct 706 ms 178424 KB Output is correct
3 Correct 777 ms 180984 KB Output is correct
4 Correct 729 ms 178164 KB Output is correct
5 Correct 719 ms 178556 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 632 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 4 ms 1400 KB Output is correct
5 Correct 4 ms 1400 KB Output is correct
6 Correct 4 ms 1404 KB Output is correct
7 Correct 4 ms 1400 KB Output is correct
8 Correct 4 ms 1400 KB Output is correct
9 Correct 4 ms 1400 KB Output is correct
10 Correct 4 ms 1400 KB Output is correct
11 Correct 81 ms 3820 KB Output is correct
12 Correct 4 ms 1528 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 7612 KB Output is correct
2 Correct 123 ms 7288 KB Output is correct
3 Correct 149 ms 7288 KB Output is correct
4 Correct 158 ms 7288 KB Output is correct
5 Correct 150 ms 7416 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 552 ms 7368 KB Output is correct
10 Correct 3 ms 632 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 186232 KB Output is correct
2 Correct 687 ms 186180 KB Output is correct
3 Correct 698 ms 186332 KB Output is correct
4 Correct 719 ms 187592 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 7288 KB Output is correct
2 Correct 123 ms 7288 KB Output is correct
3 Correct 150 ms 7288 KB Output is correct
4 Correct 148 ms 7288 KB Output is correct
5 Correct 145 ms 7416 KB Output is correct
6 Correct 692 ms 186252 KB Output is correct
7 Correct 680 ms 186280 KB Output is correct
8 Correct 697 ms 186272 KB Output is correct
9 Correct 717 ms 187612 KB Output is correct
10 Correct 668 ms 178312 KB Output is correct
11 Correct 674 ms 178280 KB Output is correct
12 Correct 748 ms 181056 KB Output is correct
13 Correct 722 ms 178196 KB Output is correct
14 Correct 681 ms 178280 KB Output is correct
15 Correct 2 ms 760 KB Output is correct
16 Correct 2 ms 632 KB Output is correct
17 Correct 2 ms 760 KB Output is correct
18 Correct 4 ms 1532 KB Output is correct
19 Correct 4 ms 1400 KB Output is correct
20 Correct 4 ms 1400 KB Output is correct
21 Correct 4 ms 1424 KB Output is correct
22 Correct 4 ms 1400 KB Output is correct
23 Correct 4 ms 1400 KB Output is correct
24 Correct 4 ms 1400 KB Output is correct
25 Correct 80 ms 3768 KB Output is correct
26 Correct 4 ms 1400 KB Output is correct
27 Correct 535 ms 7376 KB Output is correct
28 Correct 1789 ms 191404 KB Output is correct
29 Correct 1835 ms 187924 KB Output is correct
30 Correct 1932 ms 188212 KB Output is correct
31 Correct 1831 ms 192996 KB Output is correct
32 Correct 2 ms 764 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 7408 KB Output is correct
2 Correct 123 ms 7352 KB Output is correct
3 Correct 149 ms 7416 KB Output is correct
4 Correct 148 ms 7260 KB Output is correct
5 Correct 146 ms 7288 KB Output is correct
6 Correct 678 ms 186284 KB Output is correct
7 Correct 677 ms 186232 KB Output is correct
8 Correct 702 ms 186360 KB Output is correct
9 Correct 723 ms 187640 KB Output is correct
10 Correct 675 ms 178236 KB Output is correct
11 Correct 687 ms 178440 KB Output is correct
12 Correct 739 ms 181132 KB Output is correct
13 Correct 684 ms 178256 KB Output is correct
14 Correct 669 ms 178168 KB Output is correct
15 Correct 2103 ms 197772 KB Output is correct
16 Correct 5866 ms 199092 KB Output is correct
17 Correct 2 ms 632 KB Output is correct
18 Correct 2 ms 760 KB Output is correct
19 Correct 2 ms 632 KB Output is correct
20 Correct 4 ms 1400 KB Output is correct
21 Correct 4 ms 1400 KB Output is correct
22 Correct 4 ms 1400 KB Output is correct
23 Correct 4 ms 1400 KB Output is correct
24 Correct 4 ms 1404 KB Output is correct
25 Correct 4 ms 1400 KB Output is correct
26 Correct 4 ms 1400 KB Output is correct
27 Correct 80 ms 3832 KB Output is correct
28 Correct 4 ms 1528 KB Output is correct
29 Correct 539 ms 7292 KB Output is correct
30 Correct 1794 ms 191352 KB Output is correct
31 Correct 4698 ms 196404 KB Output is correct
32 Correct 4693 ms 196420 KB Output is correct
33 Correct 1825 ms 187924 KB Output is correct
34 Correct 4991 ms 192812 KB Output is correct
35 Correct 1863 ms 187912 KB Output is correct
36 Correct 5106 ms 192884 KB Output is correct
37 Correct 1839 ms 192920 KB Output is correct
38 Correct 4802 ms 196912 KB Output is correct
39 Correct 3 ms 760 KB Output is correct
40 Correct 5274 ms 192688 KB Output is correct