Submission #1265643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265643		kl0989e	Wombats (IOI13_wombats)	C++20	55 / 100	4393 ms	327680 KiB

wombats

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

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

vector<vi> v(5000,vi(200,0)),h(5000,vi(200,0));
int n,m;

struct segTree {
    struct node {
        vector<vi> dp;

        node(int i=-1) {
            if (i==-1) {
                return;
            }
            dp.resize(m,vi(m,1e9));
            for (int j=0; j<m; j++) {
                dp[j][j]=0;
                for (int j2=j+1; j2<m; j2++) {
                    dp[j][j2]=dp[j][j2-1]+h[i][j2-1];
                    dp[j2][j]=dp[j][j2];
                }
            }
            for (int j=0; j<m; j++) {
                for (int j2=0; j2<m; j2++) {
                    dp[j][j2]+=v[i][j2];
                }
                for (int j2=0; j2<m-1; j2++) {
                    dp[j][j2+1]=min(dp[j][j2+1],dp[j][j2]+h[i+1][j2]);
                }
                for (int j2=m-2; j2>=0; j2--) {
                    dp[j][j2]=min(dp[j][j2],dp[j][j2+1]+h[i+1][j2]);
                }
            }
        }
    };

    node unite(node& a, node& b) {
        node ret=node();
        ret.dp.resize(m,vi(m,1e9));
        vector<vi> opt(m,vi(m));
        for (int i=m-1; i>=0; i--) {
            for (int j=0; j<m; j++) {
                int l=(j==0?0:opt[i][j-1]);
                int r=(i==m-1?m-1:opt[i+1][j]);
                for (int k=l; k<=r; k++) {
                    if (ret.dp[i][j]>a.dp[i][k]+b.dp[k][j]) {
                        opt[i][j]=k;
                        ret.dp[i][j]=a.dp[i][k]+b.dp[k][j];
                    }
                }
            }
        }
        return ret;
    }

    vector<node> nodes;

    segTree(bool ok=0) {
        if (ok==0) {
            return;
        }
        nodes.resize(4*n);
        build(1,0,n-2);
    }

    void build(int vv, int tl, int tr) {
        if (tl==tr) {
            nodes[vv]=node(tl);
            return;
        }
        int tm=tl+(tr-tl)/2;
        build(2*vv,tl,tm);
        build(2*vv+1,tm+1,tr);
        nodes[vv]=unite(nodes[2*vv],nodes[2*vv+1]);
    }

    void update(int ind, int vv, int tl, int tr) {
        if (tl==tr) {
            nodes[vv]=node(tl);
            return;
        }
        int tm=tl+(tr-tl)/2;
        if (ind<=tm) {
            build(2*vv,tl,tm);
        }
        else {
            build(2*vv+1,tm+1,tr);
        }
        nodes[vv]=unite(nodes[2*vv],nodes[2*vv+1]);
    }
    void update(int ind) {
        update(ind,1,0,n-2);
    }

    int get(int l, int r) {
        return nodes[1].dp[l][r];
    }
};

segTree dat;

void init(int r, int c, int hh[5000][200], int vv[5000][200]) {
    n=r;
    m=c;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m-1; j++) {
            h[i][j]=hh[i][j];
        }
    }
    for (int i=0; i<n-1; i++) {
        for (int j=0; j<m; j++) {
            v[i][j]=vv[i][j];
        }
    }
    segTree tdata(1);
    swap(dat,tdata);
}

void changeH(int p, int q, int w) {
    h[p][q]=w;
    if (p!=0) {
        dat.update(p-1);
    }
    if (p!=n-1) {
        dat.update(p);
    }
}

void changeV(int p, int q, int w) {
    v[p][q]=w;
    dat.update(p);
}

int escape(int v1, int v2) {
    return dat.get(v1,v2);
}

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