제출 #1219503

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219503		HappyCapybara	Wombats (IOI13_wombats)	C++20	27 / 100	169 ms	327680 KiB

wombats

#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;

int R, C;
vector<vector<int>> d, l, r;
vector<vector<vector<int>>> st;
vector<vector<int>> opt;

void calc(int node, int tl, int tr){
    //cout << tl << " " << tr << endl;
    vector<int> ps1(C, 0), ps2(C, 0);
    for (int i=0; i<C-1; i++){
        ps1[i+1] = ps1[i]+r[tl][i];
        ps2[i+1] = ps2[i]+r[tr][i];
    }
    for (int i=0; i<C; i++){
        st[node][i][i] = 1<<25;
        for (int j=0; j<C; j++){
            int k = abs(ps1[j]-ps1[i])+abs(ps2[j]-ps2[i])+d[tl][j];
            if (k < st[node][i][i]){
                opt[i][i] = j;
                st[node][i][i] = k;
            }
        }
    }
    for (int dif=1; dif<C; dif++){
        for (int i=0; i+dif<C; i++){
            st[node][i][i+dif] = 1<<25;
            for (int j=opt[i][i+dif-1]; j<=opt[i+1][i+dif]; j++){
                int k = abs(ps1[i]-ps1[j])+abs(ps2[i+dif]-ps2[j])+d[tl][j];
                if (k < st[node][i][i+dif]){
                    opt[i][i+dif] = j;
                    st[node][i][i+dif] = k;
                }
            }
            st[node][i+dif][i] = 1<<25;
            for (int j=opt[i+dif-1][i]; j<=opt[i+dif][i+1]; j++){
                int k = abs(ps1[i+dif]-ps1[j])+abs(ps2[i]-ps2[j])+d[tl][j];
                if (k < st[node][i+dif][i]){
                    opt[i+dif][i] = j;
                    st[node][i+dif][i] = k;
                }
            }
        }
    }
    /*for (int i=0; i<C; i++){
        for (int j=0; j<C; j++) cout << st[node][i][j] << " ";
        cout << endl;
    }*/
}

void merge(int node){
    int l = node*2, r = node*2+1;
    for (int i=0; i<C; i++){
        st[node][i][i] = 1<<25;
        for (int j=0; j<C; j++){
            if (st[l][i][j]+st[r][j][i] < st[node][i][i]){
                opt[i][i] = j;
                st[node][i][i] = st[l][i][j]+st[r][j][i];
            }
        }
    }
    for (int dif=1; dif<C; dif++){
        for (int i=0; i+dif<C; i++){
            st[node][i][i+dif] = 1<<25;
            for (int j=opt[i][i+dif-1]; j<=opt[i+1][i+dif]; j++){
                if (st[l][i][j]+st[r][j][i+dif] < st[node][i][i+dif]){
                    opt[i][i+dif] = j;
                    st[node][i][i+dif] = st[l][i][j]+st[r][j][i+dif];
                }
            }
            st[node][i+dif][i] = 1<<25;
            for (int j=opt[i+dif-1][i]; j<=opt[i+dif][i+1]; j++){
                if (st[l][i+dif][j]+st[r][j][i] < st[node][i+dif][i]){
                    opt[i+dif][i] = j;
                    st[node][i+dif][i] = st[l][i+dif][j]+st[r][j][i];
                }
            }
        }
    }
}

void update(int pos, int node=1, int tl=0, int tr=R-1){
    if (tl+1 == tr){
        calc(node, tl, tr);
        return;
    }
    int tm = (tl+tr)/2;
    if (pos <= tm) update(pos, node*2, tl, tm);
    if (tm <= pos) update(pos, node*2+1, tm, tr);
    merge(node);
}

void build(int node=1, int tl=0, int tr=R-1){
    if (tl+1 == tr){
        calc(node, tl, tr);
        return;
    }
    int tm = (tl+tr)/2;
    build(node*2, tl, tm);
    build(node*2+1, tm, tr);
    merge(node);
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    ::R = R; ::C = C;
    d.resize(R, vector<int>(C));
    l.resize(R, vector<int>(C));
    r.resize(R, vector<int>(C));
    for (int i=0; i<R; i++){
        for (int j=0; j<C; j++){
            if (i < R-1) d[i][j] = V[i][j];
            if (j > 0) l[i][j] = H[i][j-1];
            if (j < C-1) r[i][j] = H[i][j];
        }
    }
    st.resize(1<<14+5, vector<vector<int>>(C, vector<int>(C)));
    opt.resize(C, vector<int>(C));
    build();
}

void changeH(int P, int Q, int W) {
    r[P][Q] = W;
    l[P][Q+1] = W;
    update(P);
}

void changeV(int P, int Q, int W) {
    d[P][Q] = W;
    update(P);
}

int escape(int V1, int V2) {
    return st[1][V1][V2];
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24