Submission #1140913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140913		urosk	Wombats (IOI13_wombats)	C++20	28 / 100	839 ms	327680 KiB

wombats

#include "wombats.h"
#include "bits/stdc++.h"
#define here cerr<<"=======================================\n"
using ll = int;

using namespace std;
const ll maxn = 10005;
const ll maxh = 205;
const ll llinf = 2000000000;
ll n,m;
ll t[maxh][maxh][maxn/10], ls[maxn/10],rs[maxn/10];
ll a[maxn/2][maxh];
ll b[maxn/2][maxh];
ll tsz = 0,root = 0;
ll ps[maxh];
ll pre[maxn/2];
ll ide[maxn/2];
ll c[maxh];
ll pm[maxh];
ll sm[maxh];
ll opt[maxh][maxh];
ll nw[maxh][maxh];
void iit(ll &v,ll tl,ll tr) {
    if(!v) v = ++tsz;
    if(tl+10>=tr) {
        for(ll i = 2;i<=m;i++) ps[i] = ps[i-1] + a[tl][i-1];
        for(ll i = 1;i<=m;i++) {
            for(ll j = 1;j<=m;j++) t[i][j][v] = ps[max(i,j)]-ps[min(i,j)];
        }
        for(ll k = tl;k<tr;k++) {
            for(ll i = 2;i<=m;i++) ps[i] = ps[i-1] + a[k+1][i-1];
            pm[0] = llinf;
            sm[m+1] = llinf;
            for(ll i = 1;i<=m;i++) {
                for(ll j = 1;j<=m;j++) pm[j] = min(pm[j-1],t[i][j][v] + b[k][j] - ps[j]);
                for(ll j = m;j>=1;j--) sm[j] = min(sm[j+1],t[i][j][v] + b[k][j] + ps[j]);
                for(ll j = 1;j<=m;j++) {
                    nw[i][j] = min(ps[j]+pm[j],sm[j]-ps[j]);
                }
            }
            for(ll i = 1;i<=m;i++) for(ll j = 1;j<=m;j++) t[i][j][v] = nw[i][j];
        }
        for(ll k = tl;k<=tr;k++) ide[k] = v;
        for(ll k = tl;k<tr;k++) pre[k] = v;
        return;
    }
    ll mid = (tl+tr)/2;
    iit(ls[v],tl,mid);
    iit(rs[v],mid+1,tr);
    for(ll i = 0;i<=m+1;i++) for(ll j = 0;j<=m+1;j++) opt[i][j] = -1;
    for(ll len = 0;len<=m-1;len++) {
        for(ll i = 1;i+len<=m;i++) {
            ll j = i+len;
            ll lb = opt[i][j-1]!=-1?opt[i][j-1]:1;
            ll rb = opt[i+1][j]!=-1?opt[i+1][j]:m;
            t[i][j][v] = llinf;
            for(ll k = lb;k<=rb;k++) {
                ll cur = t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k];
                if(cur<t[i][j][v]) {
                    t[i][j][v] = cur;
                    opt[i][j] = k;
                }
            }
        }
    }
    for(ll len = 0;len<=m-1;len++) {
        for(ll i = m;i>=len+1;i--) {
            ll j = i-len;
            ll lb = opt[i-1][j]!=-1?opt[i-1][j]:1;
            ll rb = opt[i][j+1]!=-1?opt[i][j+1]:m;
            t[i][j][v] = llinf;
            for(ll k = lb;k<=rb;k++) {
                ll cur = t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k];
                if(cur<t[i][j][v]) {
                    t[i][j][v] = cur;
                    opt[i][j] = k;
                }
            }
        }
    }
    pre[mid] = v;
}
void upd(ll v,ll tl,ll tr,ll id) {
    ll mid = (tl+tr)/2;
    //cerr<<id<< " "<<v<< " "<<ls[v]<< " "<<rs[v]<<endl;
    if(v==id) {
        if(tl+10>=tr) {
            for(ll i = 2;i<=m;i++) ps[i] = ps[i-1] + a[tl][i-1];
            for(ll i = 1;i<=m;i++) {
                for(ll j = 1;j<=m;j++) t[i][j][v] = ps[max(i,j)]-ps[min(i,j)];
            }
            for(ll k = tl;k<tr;k++) {
                for(ll i = 2;i<=m;i++) ps[i] = ps[i-1] + a[k+1][i-1];
                pm[0] = llinf;
                sm[m+1] = llinf;
                for(ll i = 1;i<=m;i++) {
                    for(ll j = 1;j<=m;j++) pm[j] = min(pm[j-1],t[i][j][v] + b[k][j] - ps[j]);
                    for(ll j = m;j>=1;j--) sm[j] = min(sm[j+1],t[i][j][v] + b[k][j] + ps[j]);
                    for(ll j = 1;j<=m;j++) {
                        nw[i][j] = min(ps[j]+pm[j],sm[j]-ps[j]);
                    }
                }
                for(ll i = 1;i<=m;i++) for(ll j = 1;j<=m;j++) t[i][j][v] = nw[i][j];
            }
            return;
        }else {
            for(ll i = 0;i<=m+1;i++) for(ll j = 0;j<=m+1;j++) opt[i][j] = -1;
            for(ll len = 0;len<=m-1;len++) {
                for(ll i = 1;i+len<=m;i++) {
                    ll j = i+len;
                    ll lb = opt[i][j-1]!=-1?opt[i][j-1]:1;
                    ll rb = opt[i+1][j]!=-1?opt[i+1][j]:m;
                    t[i][j][v] = llinf;
                    for(ll k = lb;k<=rb;k++) {
                        ll cur = t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k];
                        if(cur<t[i][j][v]) {
                            t[i][j][v] = cur;
                            opt[i][j] = k;
                        }
                    }
                }
            }
            for(ll len = 0;len<=m-1;len++) {
                for(ll i = m;i>=len+1;i--) {
                    ll j = i-len;
                    ll lb = opt[i-1][j]!=-1?opt[i-1][j]:1;
                    ll rb = opt[i][j+1]!=-1?opt[i][j+1]:m;
                    t[i][j][v] = llinf;
                    for(ll k = lb;k<=rb;k++) {
                        ll cur = t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k];
                        if(cur<t[i][j][v]) {
                            t[i][j][v] = cur;
                            opt[i][j] = k;
                        }
                    }
                }
            }
            //cerr<<"A";
        }
        return;
    }
    if(id<rs[v]) upd(ls[v],tl,mid,id);
    else upd(rs[v],mid+1,tr,id);
    for(ll i = 0;i<=m+1;i++) for(ll j = 0;j<=m+1;j++) opt[i][j] = -1;
    for(ll len = 0;len<=m-1;len++) {
        for(ll i = 1;i+len<=m;i++) {
            ll j = i+len;
            ll lb = opt[i][j-1]!=-1?opt[i][j-1]:1;
            ll rb = opt[i+1][j]!=-1?opt[i+1][j]:m;
            t[i][j][v] = llinf;
            for(ll k = lb;k<=rb;k++) {
                ll cur = t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k];
                if(cur<t[i][j][v]) {
                    t[i][j][v] = cur;
                    opt[i][j] = k;
                }
            }
        }
    }
    for(ll len = 0;len<=m-1;len++) {
        for(ll i = m;i>=len+1;i--) {
            ll j = i-len;
            ll lb = opt[i-1][j]!=-1?opt[i-1][j]:1;
            ll rb = opt[i][j+1]!=-1?opt[i][j+1]:m;
            t[i][j][v] = llinf;
            for(ll k = lb;k<=rb;k++) {
                ll cur = t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k];
                if(cur<t[i][j][v]) {
                    t[i][j][v] = cur;
                    opt[i][j] = k;
                }
            }
        }
    }
    // cerr<<id<< " "<<v<< " "<<ls[v]<< " "<<rs[v]<<" "<<222222<<endl;
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = R,m = C;
    for(ll i = 1;i<=n;i++) {
        for(ll j = 1;j<=m;j++) a[i][j] = H[i-1][j-1],b[i][j] = V[i-1][j-1];
    }
    iit(root,1,n);
}

void changeH(int P, int Q, int W) {
    ll x = P+1,y = Q+1,w = W;
    a[x][y] = w;
    upd(root,1,n,ide[x]);
    //cerr<<"B"<<endl;
}

void changeV(int P, int Q, int W) {
    ll x = P+1,y = Q+1,w = W;
    b[x][y] = w;
    upd(root,1,n,pre[x]);
}

int escape(int V1, int V2) {
    V1++,V2++;
    //cerr<<V1<< " "<<V2<<endl;
    return t[V1][V2][root];
}

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