oj.uz

Submission #597747

# Submission time Handle Problem Language Result Execution time Memory
597747 2022-07-16T19:08:00 Z AlperenT Wombats (IOI13_wombats) C++17
28 / 100
 558 ms 177116 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[1000];

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

# Verdict Execution time Memory Grader output
1 Incorrect 441 ms 173272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10580 KB Output is correct
2 Correct 6 ms 10580 KB Output is correct
3 Correct 5 ms 10580 KB Output is correct
4 Correct 8 ms 12856 KB Output is correct
5 Correct 7 ms 12884 KB Output is correct
6 Correct 7 ms 12856 KB Output is correct
7 Correct 8 ms 12884 KB Output is correct
8 Correct 9 ms 12852 KB Output is correct
9 Correct 9 ms 12884 KB Output is correct
10 Correct 8 ms 12800 KB Output is correct
11 Correct 78 ms 15196 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 155 ms 17648 KB Output is correct
2 Correct 128 ms 17636 KB Output is correct
3 Correct 164 ms 17648 KB Output is correct
4 Correct 161 ms 17620 KB Output is correct
5 Correct 161 ms 17612 KB Output is correct
6 Correct 6 ms 10580 KB Output is correct
7 Correct 5 ms 10580 KB Output is correct
8 Correct 5 ms 10660 KB Output is correct
9 Correct 558 ms 17652 KB Output is correct
10 Correct 6 ms 12116 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 423 ms 177004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 17652 KB Output is correct
2 Correct 125 ms 17640 KB Output is correct
3 Correct 166 ms 17612 KB Output is correct
4 Correct 185 ms 17772 KB Output is correct
5 Correct 157 ms 17608 KB Output is correct
6 Incorrect 423 ms 177116 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 17612 KB Output is correct
2 Correct 123 ms 17636 KB Output is correct
3 Correct 170 ms 17576 KB Output is correct
4 Correct 169 ms 17648 KB Output is correct
5 Correct 157 ms 17648 KB Output is correct
6 Incorrect 432 ms 177100 KB Output isn't correct
7 Halted 0 ms 0 KB -