제출 #614185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
614185		keta_tsimakuridze	웜뱃 (IOI13_wombats)	C++14	100 / 100	6835 ms	184548 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
#define ll int
using namespace std;
const int ROW = 5002, COL = 202, B = 10;
int INF = 2e9;
int h[ROW][COL], v[ROW][COL],C,R;
struct node {
    ll d[COL][COL];
} tree[4 * ROW / 10];

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;

            if(j < C) { c.d[i][j] = INF;
                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];
}

컴파일 시 표준 에러 (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