oj.uz

Submission #614150

# Submission time Handle Problem Language Result Execution time Memory
614150 2022-07-30T20:07:21 Z keta_tsimakuridze Wombats (IOI13_wombats) C++14
76 / 100
 2450 ms 110960 KB 
#include "wombats.h"
#include <bits/stdc++.h>
#define ll int
using namespace std;
const int ROW = 5002, COL = 202, B = 20;
int INF = 2e9;
int h[ROW][COL], v[ROW][COL],C,R;
struct node {
    ll d[COL][COL];
} tree[4 * ROW / 16];

node merge(node a, node b, int mid) {
    node c = a;
    vector<vector<int> > opt;
    opt.resize(C, vector<int>(C ));
    for(int i = 0; i < C; i++) {
        for(int j = 0; j < C; j++) {
            a.d[i][j] += v[mid][j];
        }
    }
    for(int i = 0; i < C; i++) {
        c.d[i][i] = INF;
        for(int j = 0; j < C; j++) {
            if(c.d[i][i] > a.d[i][j] + b.d[j][i]) {
                opt[i][i] = j;
                c.d[i][i]= a.d[i][j] + b.d[j][i];
            }
        }
    }
    for(int X = 1; X < C; X++) {
        // i x j
        for(int i = 0; i < C; i++) {
            int j = i + X;
            c.d[i][j] = INF;
            if(j < C) {
                for(int k = opt[i][j - 1]; k <= opt[i + 1][j]; k++) {
                    if(c.d[i][j] > a.d[i][k] + b.d[k][j]) {
                        c.d[i][j] = a.d[i][k] + b.d[k][j];
                        opt[i][j] = k;
                    }
                }
            }

            j = i - X;

            if(j >= 0) {
                c.d[i][j] = INF;
                for(int k = opt[i - 1][j]; k <= opt[i][j + 1]; k++) {
                    if(c.d[i][j] > a.d[i][k] + b.d[k][j]) {
                        c.d[i][j] = a.d[i][k] + b.d[k][j];
                        opt[i][j] = k;
                    }
                }
            }
        }
    }
    return c;
}

node get(int l, int r) {
    if(l == r) {
        node a;
        for(int i = 0; i < C; i++) {
            a.d[i][i] = 0;
            for(int j = i + 1; j < C; j++) {
                a.d[i][j] = a.d[i][j - 1] + h[l][j - 1];
            }

            for(int j = i - 1; j >= 0; j--) {
                a.d[i][j] = a.d[i][j + 1] + h[l][j];
            }
        }
        return a;
    }
    int mid = (l + r) / 2;
    return merge(get(l, mid), get(mid + 1, r), mid);
}

void build(int u,int l, int r) {
    if(r - l + 1 <= B) {
        tree[u] = get(l, r);
        return;
    }
    int mid = (l + r)  / 2;
    build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);

    tree[u] = merge(tree[2 * u], tree[2 * u + 1], mid);
}

void upd(int u,int id, int l, int r) {
    if(l > id || r < id) return;
    if(r - l + 1 <= B) {
        tree[u] = get(l, r);
        return;
    }
    int mid = (l + r) / 2;
    upd(2 * u, id, l, mid); upd(2 * u + 1, id, mid + 1, r);
    tree[u] = merge(tree[2 * u], tree[2 * u + 1], mid);
}

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

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    upd(1, P, 0, R);
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    upd(1, P, 0, R);
}

int escape(int V1, int V2) {
    return tree[1].d[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]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 97100 KB Output is correct
2 Correct 552 ms 97108 KB Output is correct
3 Correct 598 ms 99916 KB Output is correct
4 Correct 573 ms 97104 KB Output is correct
5 Correct 609 ms 97108 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 2 ms 2516 KB Output is correct
5 Correct 2 ms 2608 KB Output is correct
6 Correct 2 ms 2516 KB Output is correct
7 Correct 2 ms 2516 KB Output is correct
8 Correct 2 ms 2516 KB Output is correct
9 Correct 2 ms 2516 KB Output is correct
10 Correct 2 ms 2516 KB Output is correct
11 Correct 66 ms 4976 KB Output is correct
12 Correct 2 ms 2516 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 5508 KB Output is correct
2 Correct 173 ms 5372 KB Output is correct
3 Correct 261 ms 5488 KB Output is correct
4 Correct 247 ms 5384 KB Output is correct
5 Correct 238 ms 5380 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 828 ms 5432 KB Output is correct
10 Correct 1 ms 1620 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 101044 KB Output is correct
2 Correct 548 ms 101124 KB Output is correct
3 Correct 575 ms 101056 KB Output is correct
4 Correct 649 ms 102348 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 5384 KB Output is correct
2 Correct 183 ms 5316 KB Output is correct
3 Correct 234 ms 5368 KB Output is correct
4 Correct 237 ms 5308 KB Output is correct
5 Correct 237 ms 5384 KB Output is correct
6 Correct 601 ms 101060 KB Output is correct
7 Correct 589 ms 101064 KB Output is correct
8 Correct 597 ms 100936 KB Output is correct
9 Correct 660 ms 102332 KB Output is correct
10 Correct 600 ms 97208 KB Output is correct
11 Correct 559 ms 97132 KB Output is correct
12 Correct 629 ms 99876 KB Output is correct
13 Correct 689 ms 97104 KB Output is correct
14 Correct 597 ms 97112 KB Output is correct
15 Correct 1 ms 1236 KB Output is correct
16 Correct 1 ms 1236 KB Output is correct
17 Correct 1 ms 1236 KB Output is correct
18 Correct 2 ms 2516 KB Output is correct
19 Correct 2 ms 2612 KB Output is correct
20 Correct 2 ms 2616 KB Output is correct
21 Correct 2 ms 2516 KB Output is correct
22 Correct 2 ms 2516 KB Output is correct
23 Correct 3 ms 2516 KB Output is correct
24 Correct 3 ms 2516 KB Output is correct
25 Correct 77 ms 4960 KB Output is correct
26 Correct 3 ms 2516 KB Output is correct
27 Correct 844 ms 5384 KB Output is correct
28 Correct 2310 ms 105208 KB Output is correct
29 Correct 2438 ms 101708 KB Output is correct
30 Correct 2450 ms 102080 KB Output is correct
31 Correct 2339 ms 106848 KB Output is correct
32 Correct 1 ms 1620 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 5512 KB Output is correct
2 Correct 166 ms 5368 KB Output is correct
3 Correct 254 ms 5456 KB Output is correct
4 Correct 256 ms 5380 KB Output is correct
5 Correct 235 ms 5384 KB Output is correct
6 Correct 545 ms 101064 KB Output is correct
7 Correct 582 ms 101040 KB Output is correct
8 Correct 555 ms 101060 KB Output is correct
9 Correct 655 ms 102380 KB Output is correct
10 Correct 621 ms 97172 KB Output is correct
11 Correct 570 ms 97112 KB Output is correct
12 Correct 630 ms 99852 KB Output is correct
13 Correct 543 ms 97100 KB Output is correct
14 Correct 646 ms 97204 KB Output is correct
15 Incorrect 2196 ms 110960 KB Output isn't correct
16 Halted 0 ms 0 KB -