Submission #597748

#	Time	Username	Problem	Language	Result	Execution time	Memory
597748		AlperenT	Wombats (IOI13_wombats)	C++17	100 / 100	7178 ms	192096 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24