Submission #18060

#	Time	Username	Problem	Language	Result	Execution time	Memory
18060		comet	Wombats (IOI13_wombats)	C++98	100 / 100	12160 ms	67528 KiB

wombats

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#include "wombats.h"

int R,C;
int H[5000][200];
int V[5000][200];
int D[5000][200];

void make_dp(int s,int e,int v1,int dp[]){
	D[s][v1]=0;
	int sum=0;
	for(int i=v1-1;i>=0;i--){
		sum+=H[s][i];
		D[s][i]=sum;
	}
	sum=0;
	for(int i=v1;i<C-1;i++){
		sum+=H[s][i];
		D[s][i+1]=sum;
	}

	int l[5000],r[5000];

	for(int i=s+1;i<=e;i++){
		for(int j=0;j<C;j++){
			l[j]=D[i-1][j]+V[i-1][j];
			if(j)l[j]=min(l[j],l[j-1]+H[i][j-1]);
		}
		for(int j=C-1;j>=0;j--){
			r[j]=D[i-1][j]+V[i-1][j];
			if(j<C-1)r[j]=min(r[j],r[j+1]+H[i][j]);
		}
		for(int j=0;j<C;j++){
			D[i][j]=min(l[j],r[j]);
		}
	}

	for(int i=0;i<C;i++)dp[i]=D[e][i];
}

#define LL 2*k+1
#define RR 2*k+2

struct Node{
	int s,e;
	int dp[200][200];

	void init(){
		for(int i=0;i<C;i++){
			make_dp(s,e,i,dp[i]);
		}
	}
}tree[300];

void up(int k){
	int y=tree[LL].e;
	int opt[200][200];
	for(int i=0;i<C;i++){
		for(int j=C-1;j>=0;j--){
			tree[k].dp[i][j]=1e9;
			for(int m=(i==0?0:opt[i-1][j]);m<=(j==C-1?C-1:opt[i][j+1]);m++){
				if(tree[k].dp[i][j]>tree[LL].dp[i][m]+V[y][m]+tree[RR].dp[m][j]){
					tree[k].dp[i][j]=tree[LL].dp[i][m]+V[y][m]+tree[RR].dp[m][j];
					opt[i][j]=m;
				}
			}
		}
	}
}

void update(int x,int k){
	if(tree[k].s+50>tree[k].e){
		tree[k].init();
		return;
	}
	int mid=(tree[k].s+tree[k].e)/2;
	if(x<=mid)update(x,LL);
	else update(x,RR);
	up(k);
}

void make_tree(int s,int e,int k){
	tree[k].s=s;
	tree[k].e=e;
	if(s+50>e){
		tree[k].init();
		return;
	}
	int mid=(s+e)/2;
	make_tree(s,mid,LL);
	make_tree(mid+1,e,RR);
	up(k);
}

#undef LL
#undef RR

void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
	R=_R;
	C=_C;
	for(int i=0;i<R;i++){
		for(int j=0;j<C-1;j++){
			H[i][j]=_H[i][j];
		}
	}
	for(int i=0;i<R-1;i++){
		for(int j=0;j<C;j++){
			V[i][j]=_V[i][j];
		}
	}
	make_tree(0,R-1,0);
}

void changeH(int P, int Q, int W) {

	H[P][Q]=W;

	update(P,0);
}

void changeV(int P, int Q, int W) {

	V[P][Q]=W;

	update(P,0);
}

int escape(int v1, int v2) {
	return tree[0].dp[v1][v2];
}	

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