Submission #1199344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199344		Hamed_Ghaffari	웜뱃 (IOI13_wombats)	C++20	55 / 100	244 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)

const int B = 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];
inline void merge(vc<vc<int>> &A, vc<vc<int>> &B, vc<vc<int>> &C) { // O(m2)
    for(int i=0; i<m; i++)
        fill(C[i].begin(), C[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(A[i][k]+B[k][j]<C[i][j]) {
                    opt[i][j] = k;
                    C[i][j] = A[i][k] + B[k][j];
                }
}

inline void build_row(int i, vc<vc<int>> &A) { // O(m2)
    for(int j=0; j<m; j++) {
        for(int k=j, sum=0; k<m; k++) {
            A[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];
            A[j][k] = sum + V[i][k];
        }
    }
}

vc<vc<int>> tmp1, tmp2;

inline void build_block(int b) { // O(Bm2)
    build_row(b*B, seg[wh[b]]);
    for(int i=b*B+1; i<(b+1)*B && i+1<n; i++) {
        build_row(i, tmp1);
        merge(seg[wh[b]], tmp1, tmp2);
        seg[wh[b]] = tmp2;
    }
}

void build(int l=0, int r=(n+B-1)/B, int id=0) { // O(nm2)
    if(r-l == 1) {
        wh[l] = id;
        build_block(l);
        return;
    }
    lc[id] = ++N;
    rc[id] = ++N;
    build(l, mid, lc[id]);
    build(mid, r, rc[id]);
    merge(seg[lc[id]], seg[rc[id]], seg[id]);
}
void upd(int p, int l=0, int r=(n+B-1)/B, int id=0) { // O(Bm2logn)
    if(r-l == 1) {
        build_block(p);
        return;
    }
    p<mid ? upd(p, l, mid, lc[id]) : upd(p, mid, r, rc[id]);
    merge(seg[lc[id]], seg[rc[id]], seg[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+::B-1)/::B)-1, vc<vc<int>>(m, vc<int>(m)));
    tmp1 = vc<vc<int>>(m, vc<int>(m));
    tmp2 = vc<vc<int>>(m, vc<int>(m));
    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