제출 #1199340

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199340		Hamed_Ghaffari	Wombats (IOI13_wombats)	C++20	55 / 100	241 ms	327680 KiB

wombats

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

#define vc vector
#define mins(a,b) (a=min(a,b))
#define mid ((l+r)>>1)

int n, m, H[5000][200], V[5000][200], wh[5000], N, lc[10000], rc[10000];
vc<vc<vc<int>>> seg;
int opt[200][200];

void build_row(int i) { // O(m2)
    for(int j=0; j<m; j++) {
        for(int k=j, sum=0; k<m; k++) {
            seg[wh[i]][j][k] = sum + V[i][k];
            if(k+1<m) sum += H[i][k];
        }
        for(int k=j-1, sum=0; k>=0; k--) {
            sum += H[i][k];
            seg[wh[i]][j][k] = sum + V[i][k];
        }
    }
}

inline void pull(int id) { // O(m2)
    for(int i=0; i<m; i++)
        fill(seg[id][i].begin(), seg[id][i].end(), 2e9);
    for(int dif=-(m-1); dif<=(m-1); dif++)
        for(int i=max(-dif, 0), j=i+dif; i<m && j<m; i++, j++)
            for(int k=(j ? opt[i][j-1] : 0); k<=(i+1<m ? opt[i+1][j] : m-1); k++)
                if(seg[lc[id]][i][k]+seg[rc[id]][k][j]<seg[id][i][j]) {
                    opt[i][j] = k;
                    seg[id][i][j] = seg[lc[id]][i][k] + seg[rc[id]][k][j];
                }
}
void build(int l=0, int r=n-1, int id=0) { // O(nm2)
    if(r-l == 1) {
        wh[l] = id;
        build_row(l);
        return;
    }
    lc[id] = ++N;
    rc[id] = ++N;
    build(l, mid, lc[id]);
    build(mid, r, rc[id]);
    pull(id);
}
void upd(int p, int l=0, int r=n-1, int id=0) { // O(m2logn)
    if(r-l == 1) {
        build_row(p);
        return;
    }
    p<mid ? upd(p, l, mid, lc[id]) : upd(p, mid, r, rc[id]);
    pull(id);
}

void init(int n, int m, int A[5000][200], int B[5000][200]) {
    ::n = n;
    ::m = m;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            H[i][j] = A[i][j],
            V[i][j] = B[i][j];
    seg = vc<vc<vc<int>>>(2*n-1, vc<vc<int>>(m, vc<int>(m, 0)));
    build();
}

void changeH(int i, int j, int w) {
    H[i][j] = w;
    upd(i);
}

void changeV(int i, int j, int w) {
    V[i][j] = w;
    upd(i);
}

int escape(int v1, int v2) {
    int ans = 1e9;
    for(int k=v2, sum=0; k<m; k++) {
        ans = min(ans, sum + seg[0][v1][k]);
        if(k+1<m) sum += H[n-1][k];
    }
    for(int k=v2-1, sum=0; k>=0; k--) {
        sum += H[n-1][k];
        ans = min(ans, sum + seg[0][v1][k]);
    }
    return ans;
}

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