oj.uz

Submission #597748

# Submission time Handle Problem Language Result Execution time Memory
597748 2022-07-16T19:09:24 Z AlperenT Wombats (IOI13_wombats) C++17
100 / 100
 7178 ms 192096 KB 
#include <bits/stdc++.h>
#include "wombats.h"

using namespace std;

const int N = 5000, M = 200, K = 10, INF = 1e9 + 5;

int n, m, h[N][M], v[N][M];

struct Node{
    int table[M][M];
};

struct SegTree{
    Node tree[2000];

    Node merge(Node a, Node b, int indx){
        Node c;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                a.table[i][j] += v[indx][j];
            }
        }

        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                c.table[i][j] = INF;
            }
        }

        int opt[m][m];

        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                if(a.table[i][j] + b.table[j][i] < c.table[i][i]){
                    c.table[i][i] = a.table[i][j] + b.table[j][i];
                    opt[i][i] = j;
                }
            }
        }

        for(int len = 1; len < m; len++){
            for(int i = 0; i < m; i++){
                int j = i + len;

                if(j < m){
                    for(int k = opt[i][j - 1]; k <= opt[i + 1][j]; k++){
                        if(a.table[i][k] + b.table[k][j] < c.table[i][j]){
                            c.table[i][j] = a.table[i][k] + b.table[k][j];
                            opt[i][j] = k;
                        }
                    }
                }

                j = i - len;

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

        return c;
    }

    Node getnode(int l, int r){
        if(l == r){
            Node tmp;

            for(int i = 0; i < m; i++){
                tmp.table[i][i] = 0;

                int sum = 0;

                for(int j = i - 1; j >= 0; j--){
                    sum += h[l][j];

                    tmp.table[i][j] = sum;
                }

                sum = 0;

                for(int j = i + 1; j < m; j++){
                    sum += h[l][j - 1];

                    tmp.table[i][j] = sum;
                }
            }

            return tmp;
        }
        else{
            int m = l + (r - l) / 2;

            return merge(getnode(l, m), getnode(m + 1, r), m);
        }
    }

    void build(int v = 1, int l = 0, int r = n - 1){
        if(r - l + 1 <= K) tree[v] = getnode(l, r);
        else{
            int m = l + (r - l) / 2;

            build(v * 2, l, m);
            build(v * 2 + 1, m + 1, r);

            tree[v] = merge(tree[v * 2], tree[v * 2 + 1], m);
        }
    }

    void update(int pos, int v = 1, int l = 0, int r = n - 1){
        if(r - l + 1 <= K) tree[v] = getnode(l, r);
        else{
            int m = l + (r - l) / 2;

            if(pos <= m) update(pos, v * 2, l, m);
            else update(pos, v * 2 + 1, m + 1, r);

            tree[v] = merge(tree[v * 2], tree[v * 2 + 1], m);
        }
    }
};

SegTree sgt;

void init(int R_, int C_, int H_[5000][200], int V_[5000][200]){
    n = R_, m = C_;
    memcpy(h, H_, N * M * 4), memcpy(v, V_, N * M * 4);

    sgt.build();
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;

    sgt.update(P);
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;

    sgt.update(P);
}

int escape(int V1, int V2) {
    return sgt.tree[1].table[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 435 ms 176972 KB Output is correct
2 Correct 438 ms 176844 KB Output is correct
3 Correct 486 ms 179692 KB Output is correct
4 Correct 420 ms 176916 KB Output is correct
5 Correct 446 ms 176920 KB Output is correct
6 Correct 6 ms 10580 KB Output is correct
7 Correct 6 ms 10548 KB Output is correct
8 Correct 5 ms 10580 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10580 KB Output is correct
2 Correct 7 ms 10628 KB Output is correct
3 Correct 5 ms 10580 KB Output is correct
4 Correct 9 ms 12832 KB Output is correct
5 Correct 7 ms 12884 KB Output is correct
6 Correct 7 ms 12884 KB Output is correct
7 Correct 7 ms 12756 KB Output is correct
8 Correct 8 ms 12884 KB Output is correct
9 Correct 7 ms 12884 KB Output is correct
10 Correct 7 ms 12824 KB Output is correct
11 Correct 68 ms 13776 KB Output is correct
12 Correct 7 ms 12884 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 17572 KB Output is correct
2 Correct 129 ms 17492 KB Output is correct
3 Correct 165 ms 17576 KB Output is correct
4 Correct 161 ms 17572 KB Output is correct
5 Correct 173 ms 17452 KB Output is correct
6 Correct 5 ms 10580 KB Output is correct
7 Correct 6 ms 10568 KB Output is correct
8 Correct 5 ms 10580 KB Output is correct
9 Correct 568 ms 17576 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 180732 KB Output is correct
2 Correct 435 ms 180932 KB Output is correct
3 Correct 448 ms 180872 KB Output is correct
4 Correct 483 ms 182156 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 17568 KB Output is correct
2 Correct 142 ms 17572 KB Output is correct
3 Correct 181 ms 17664 KB Output is correct
4 Correct 167 ms 17572 KB Output is correct
5 Correct 162 ms 17580 KB Output is correct
6 Correct 454 ms 180816 KB Output is correct
7 Correct 434 ms 180860 KB Output is correct
8 Correct 462 ms 180840 KB Output is correct
9 Correct 479 ms 182252 KB Output is correct
10 Correct 429 ms 176844 KB Output is correct
11 Correct 420 ms 176916 KB Output is correct
12 Correct 484 ms 179660 KB Output is correct
13 Correct 447 ms 176824 KB Output is correct
14 Correct 416 ms 176916 KB Output is correct
15 Correct 6 ms 10580 KB Output is correct
16 Correct 5 ms 10544 KB Output is correct
17 Correct 6 ms 10568 KB Output is correct
18 Correct 7 ms 12884 KB Output is correct
19 Correct 7 ms 12884 KB Output is correct
20 Correct 7 ms 12796 KB Output is correct
21 Correct 7 ms 12856 KB Output is correct
22 Correct 7 ms 12860 KB Output is correct
23 Correct 7 ms 12884 KB Output is correct
24 Correct 8 ms 12848 KB Output is correct
25 Correct 71 ms 15196 KB Output is correct
26 Correct 9 ms 12856 KB Output is correct
27 Correct 584 ms 17640 KB Output is correct
28 Correct 1845 ms 185044 KB Output is correct
29 Correct 1908 ms 183352 KB Output is correct
30 Correct 1961 ms 183288 KB Output is correct
31 Correct 1878 ms 186580 KB Output is correct
32 Correct 6 ms 12116 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 17572 KB Output is correct
2 Correct 126 ms 17588 KB Output is correct
3 Correct 164 ms 17564 KB Output is correct
4 Correct 192 ms 17572 KB Output is correct
5 Correct 163 ms 17572 KB Output is correct
6 Correct 414 ms 180712 KB Output is correct
7 Correct 456 ms 180828 KB Output is correct
8 Correct 457 ms 180876 KB Output is correct
9 Correct 463 ms 182192 KB Output is correct
10 Correct 446 ms 176956 KB Output is correct
11 Correct 442 ms 176920 KB Output is correct
12 Correct 531 ms 179692 KB Output is correct
13 Correct 467 ms 176920 KB Output is correct
14 Correct 458 ms 176924 KB Output is correct
15 Correct 2315 ms 190688 KB Output is correct
16 Correct 7178 ms 192096 KB Output is correct
17 Correct 5 ms 10580 KB Output is correct
18 Correct 5 ms 10544 KB Output is correct
19 Correct 5 ms 10580 KB Output is correct
20 Correct 8 ms 12884 KB Output is correct
21 Correct 7 ms 12884 KB Output is correct
22 Correct 7 ms 12856 KB Output is correct
23 Correct 7 ms 12884 KB Output is correct
24 Correct 7 ms 12852 KB Output is correct
25 Correct 8 ms 12884 KB Output is correct
26 Correct 7 ms 12884 KB Output is correct
27 Correct 72 ms 15240 KB Output is correct
28 Correct 7 ms 12884 KB Output is correct
29 Correct 586 ms 17644 KB Output is correct
30 Correct 1888 ms 185168 KB Output is correct
31 Correct 5848 ms 189628 KB Output is correct
32 Correct 5806 ms 189384 KB Output is correct
33 Correct 1909 ms 183448 KB Output is correct
34 Correct 5945 ms 187432 KB Output is correct
35 Correct 1921 ms 183264 KB Output is correct
36 Correct 6045 ms 187412 KB Output is correct
37 Correct 1903 ms 186844 KB Output is correct
38 Correct 5948 ms 189996 KB Output is correct
39 Correct 7 ms 12128 KB Output is correct
40 Correct 6272 ms 187644 KB Output is correct