oj.uz

Submission #834736

# Submission time Handle Problem Language Result Execution time Memory
834736 2023-08-22T18:03:38 Z erdemkiraz Wombats (IOI13_wombats) C++11
100 / 100
 6614 ms 195320 KB 
#include "wombats.h"
#include "iostream"
#include "algorithm"
#include "vector"
#include "set"
#include "map"
#include "cstring"
#include "string"
#include "vector"
#include "cassert"
#include "queue"
#include "cstdio"
#include "cstdlib"
#include "ctime"
#include "cmath"
#include "bitset"
#include "numeric"
#include "iomanip"

using namespace std;

typedef long long ll;
typedef pair < int, int > ii;

const int N = 5000 + 5;
const int M = 200 + 5;

int n, m;
int a[N][M], b[N][M];
int t[1024][M][M];

void row(int i, int dp[N]) {
    for(int j = m - 1; j >= 1; j--)
        dp[j] = min(dp[j], dp[j + 1] + a[i][j]);
    for(int j = 2; j <= m; j++)
        dp[j] = min(dp[j], dp[j - 1] + a[i][j - 1]);
}

void calcDp(int x, int l, int r) {
    for(int st = 1; st <= m; st++) {
        for(int i = 1; i <= m; i++)
            t[x][st][i] = 1e9 * (st != i);
        row(l, t[x][st]);
        for(int i = l; i < r; i++) {
            for(int nd = 1; nd <= m; nd++)
                t[x][st][nd] += b[i][nd];
            row(i + 1, t[x][st]);
        }
    }
}

int opt[M][M];

void solve(int x, int x1, int x2, int i, int l, int r, int optL, int optR, int b[M]) {
    if(l > r)
        return;
    int m = (l + r) >> 1;
    int opt = -1;
    t[x][i][m] = 1e9;
    for(int j = optL; j <= optR; j++) {
        int cost = t[x1][i][j] + b[j] + t[x2][j][m];
        if(cost < t[x][i][m]) {
            t[x][i][m] = cost;
            opt = j;
        }
    }
    solve(x, x1, x2, i, l, m - 1, optL, opt, b);
    solve(x, x1, x2, i, m + 1, r, opt, optR, b);
}

void calc(int x, int x1, int x2, int b[M]) {
    for(int i = 1; i <= m; i++)
        solve(x, x1, x2, i, 1, m, 1, m, b);
}

void init(int x, int l, int r) {
    if(r - l < 15) {
        calcDp(x, l, r);
        return;
    }
    int m = (l + r) >> 1;
    init(x + x, l, m);
    init(x + x + 1, m + 1, r);
    calc(x, x + x, x + x + 1, b[m]);
}

void update(int x, int l, int r, int v) {
    if(r - l < 15) {
        calcDp(x, l, r);
        return;
    }
    int m = (l + r) >> 1;
    if(v <= m)
        update(x + x, l, m, v);
    else
        update(x + x + 1, m + 1, r, v);
    calc(x, x + x, x + x + 1, b[m]);
}

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

void changeH(int x, int y, int v) {
    ++x;
    ++y;
    a[x][y] = v;
    update(1, 1, n, x);
}

void changeV(int x, int y, int v) {
    ++x;
    ++y;
    b[x][y] = v;
    update(1, 1, n, x);
}

int escape(int x, int y) {
    ++x;
    ++y;
    return t[1][x][y];
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16596 KB Output is correct
2 Correct 7 ms 16636 KB Output is correct
3 Correct 60 ms 19352 KB Output is correct
4 Correct 7 ms 16596 KB Output is correct
5 Correct 7 ms 16596 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 55 ms 2772 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 1980 KB Output is correct
2 Correct 141 ms 1940 KB Output is correct
3 Correct 151 ms 1876 KB Output is correct
4 Correct 152 ms 1988 KB Output is correct
5 Correct 148 ms 1844 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 692 ms 1972 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 21380 KB Output is correct
2 Correct 9 ms 21460 KB Output is correct
3 Correct 9 ms 21460 KB Output is correct
4 Correct 37 ms 22816 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 2096 KB Output is correct
2 Correct 140 ms 1952 KB Output is correct
3 Correct 153 ms 1980 KB Output is correct
4 Correct 151 ms 1892 KB Output is correct
5 Correct 152 ms 1956 KB Output is correct
6 Correct 9 ms 21460 KB Output is correct
7 Correct 9 ms 21460 KB Output is correct
8 Correct 9 ms 21460 KB Output is correct
9 Correct 37 ms 22776 KB Output is correct
10 Correct 7 ms 16596 KB Output is correct
11 Correct 7 ms 16700 KB Output is correct
12 Correct 61 ms 19388 KB Output is correct
13 Correct 7 ms 16596 KB Output is correct
14 Correct 7 ms 16596 KB Output is correct
15 Correct 0 ms 304 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 436 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 440 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 55 ms 2756 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 687 ms 1984 KB Output is correct
28 Correct 1539 ms 106188 KB Output is correct
29 Correct 1487 ms 102836 KB Output is correct
30 Correct 1527 ms 102932 KB Output is correct
31 Correct 1574 ms 107980 KB Output is correct
32 Correct 1 ms 340 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 1972 KB Output is correct
2 Correct 140 ms 1876 KB Output is correct
3 Correct 152 ms 1968 KB Output is correct
4 Correct 157 ms 2080 KB Output is correct
5 Correct 148 ms 1964 KB Output is correct
6 Correct 9 ms 21460 KB Output is correct
7 Correct 9 ms 21460 KB Output is correct
8 Correct 9 ms 21460 KB Output is correct
9 Correct 36 ms 22840 KB Output is correct
10 Correct 8 ms 16660 KB Output is correct
11 Correct 7 ms 16708 KB Output is correct
12 Correct 65 ms 19420 KB Output is correct
13 Correct 6 ms 16596 KB Output is correct
14 Correct 7 ms 16688 KB Output is correct
15 Correct 1996 ms 194196 KB Output is correct
16 Correct 6613 ms 195320 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 304 KB Output is correct
20 Correct 1 ms 464 KB Output is correct
21 Correct 1 ms 440 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 444 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 54 ms 2780 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 689 ms 1972 KB Output is correct
30 Correct 1549 ms 106176 KB Output is correct
31 Correct 6442 ms 192744 KB Output is correct
32 Correct 6148 ms 192784 KB Output is correct
33 Correct 1497 ms 102860 KB Output is correct
34 Correct 6059 ms 189088 KB Output is correct
35 Correct 1729 ms 103040 KB Output is correct
36 Correct 6412 ms 189432 KB Output is correct
37 Correct 1836 ms 107884 KB Output is correct
38 Correct 6614 ms 193312 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 6402 ms 189520 KB Output is correct