답안 #18058 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18058	2016-01-19T10:47:08 Z	comet	웜뱃 (IOI13_wombats)	C++	76 / 100	20000 ms	67492 KB

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]);
		}
/*		printf("%d~%d\n",s,e);
		for(int i=0;i<C;i++,puts("")){
			for(int j=0;j<C;j++){
				printf("%d ",dp[i][j]);
			}
		}*/
	}
}tree[300];

void up(int k){
	int y=tree[LL].e;
	for(int i=0;i<C;i++){
		for(int j=0;j<C;j++){
			tree[k].dp[i][j]=1e9;
			for(int m=0;m<C;m++){
				tree[k].dp[i][j]=min(tree[k].dp[i][j],
					tree[LL].dp[i][m]+V[y][m]+tree[RR].dp[m][j]);
			}
		}
	}
}

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.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	67492 KB	Output is correct - 505 tokens
2	Correct	0 ms	67492 KB	Output is correct - 505 tokens
3	Correct	67 ms	67492 KB	Output is correct - 200005 tokens
4	Correct	0 ms	67492 KB	Output is correct - 505 tokens
5	Correct	0 ms	67492 KB	Output is correct - 505 tokens
6	Correct	0 ms	67492 KB	Output is correct - 6 tokens
7	Correct	0 ms	67492 KB	Output is correct - 6 tokens
8	Correct	0 ms	67492 KB	Output is correct - 6 tokens

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	67492 KB	Output is correct - 6 tokens
2	Correct	0 ms	67492 KB	Output is correct - 6 tokens
3	Correct	0 ms	67492 KB	Output is correct - 6 tokens
4	Correct	0 ms	67492 KB	Output is correct - 405 tokens
5	Correct	0 ms	67492 KB	Output is correct - 405 tokens
6	Correct	2 ms	67492 KB	Output is correct - 405 tokens
7	Correct	0 ms	67492 KB	Output is correct - 405 tokens
8	Correct	0 ms	67492 KB	Output is correct - 366 tokens
9	Correct	0 ms	67492 KB	Output is correct - 405 tokens
10	Correct	0 ms	67492 KB	Output is correct - 366 tokens
11	Correct	94 ms	67492 KB	Output is correct - 200005 tokens
12	Correct	0 ms	67492 KB	Output is correct - 405 tokens

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	717 ms	67492 KB	Output is correct - 105 tokens
2	Correct	711 ms	67492 KB	Output is correct - 105 tokens
3	Correct	727 ms	67492 KB	Output is correct - 105 tokens
4	Correct	725 ms	67492 KB	Output is correct - 105 tokens
5	Correct	714 ms	67492 KB	Output is correct - 105 tokens
6	Correct	0 ms	67492 KB	Output is correct - 6 tokens
7	Correct	0 ms	67492 KB	Output is correct - 6 tokens
8	Correct	0 ms	67492 KB	Output is correct - 6 tokens
9	Correct	3572 ms	67492 KB	Output is correct - 105 tokens
10	Correct	0 ms	67492 KB	Output is correct - 8 tokens

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	67492 KB	Output is correct - 1005 tokens
2	Correct	3 ms	67492 KB	Output is correct - 1005 tokens
3	Correct	3 ms	67492 KB	Output is correct - 1005 tokens
4	Correct	34 ms	67492 KB	Output is correct - 100005 tokens

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	715 ms	67492 KB	Output is correct - 105 tokens
2	Correct	713 ms	67492 KB	Output is correct - 105 tokens
3	Correct	732 ms	67492 KB	Output is correct - 105 tokens
4	Correct	725 ms	67492 KB	Output is correct - 105 tokens
5	Correct	711 ms	67492 KB	Output is correct - 105 tokens
6	Correct	8 ms	67492 KB	Output is correct - 1005 tokens
7	Correct	3 ms	67492 KB	Output is correct - 1005 tokens
8	Correct	3 ms	67492 KB	Output is correct - 1005 tokens
9	Correct	33 ms	67492 KB	Output is correct - 100005 tokens
10	Correct	0 ms	67492 KB	Output is correct - 505 tokens
11	Correct	0 ms	67492 KB	Output is correct - 505 tokens
12	Correct	62 ms	67492 KB	Output is correct - 200005 tokens
13	Correct	0 ms	67492 KB	Output is correct - 505 tokens
14	Correct	0 ms	67492 KB	Output is correct - 505 tokens
15	Correct	0 ms	67492 KB	Output is correct - 6 tokens
16	Correct	0 ms	67492 KB	Output is correct - 6 tokens
17	Correct	0 ms	67492 KB	Output is correct - 6 tokens
18	Correct	0 ms	67492 KB	Output is correct - 405 tokens
19	Correct	0 ms	67492 KB	Output is correct - 405 tokens
20	Correct	0 ms	67492 KB	Output is correct - 405 tokens
21	Correct	0 ms	67492 KB	Output is correct - 405 tokens
22	Correct	0 ms	67492 KB	Output is correct - 366 tokens
23	Correct	0 ms	67492 KB	Output is correct - 405 tokens
24	Correct	0 ms	67492 KB	Output is correct - 366 tokens
25	Correct	91 ms	67492 KB	Output is correct - 200005 tokens
26	Correct	0 ms	67492 KB	Output is correct - 405 tokens
27	Correct	3577 ms	67492 KB	Output is correct - 105 tokens
28	Correct	9642 ms	67492 KB	Output is correct - 50005 tokens
29	Correct	9188 ms	67492 KB	Output is correct - 50005 tokens
30	Correct	9180 ms	67492 KB	Output is correct - 50005 tokens
31	Correct	9745 ms	67492 KB	Output is correct - 200005 tokens
32	Correct	0 ms	67492 KB	Output is correct - 8 tokens

Subtask #6
0.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	717 ms	67492 KB	Output is correct - 105 tokens
2	Correct	712 ms	67492 KB	Output is correct - 105 tokens
3	Correct	729 ms	67492 KB	Output is correct - 105 tokens
4	Correct	723 ms	67492 KB	Output is correct - 105 tokens
5	Correct	712 ms	67492 KB	Output is correct - 105 tokens
6	Correct	8 ms	67492 KB	Output is correct - 1005 tokens
7	Correct	3 ms	67492 KB	Output is correct - 1005 tokens
8	Correct	8 ms	67492 KB	Output is correct - 1005 tokens
9	Correct	50 ms	67492 KB	Output is correct - 100005 tokens
10	Correct	0 ms	67492 KB	Output is correct - 505 tokens
11	Correct	5 ms	67492 KB	Output is correct - 505 tokens
12	Correct	79 ms	67492 KB	Output is correct - 200005 tokens
13	Correct	4 ms	67492 KB	Output is correct - 505 tokens
14	Correct	0 ms	67492 KB	Output is correct - 505 tokens
15	Correct	4747 ms	67492 KB	Output is correct - 11 tokens
16	Execution timed out	20000 ms	67492 KB	Program timed out
17	Halted	0 ms	0 KB	-

답안 #18058

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 12.0 / 12.0

Subtask #3 16.0 / 16.0

Subtask #4 18.0 / 18.0

Subtask #5 21.0 / 21.0

Subtask #6 0.0 / 24.0

Subtask #1
9.0 / 9.0

Subtask #2
12.0 / 12.0

Subtask #3
16.0 / 16.0

Subtask #4
18.0 / 18.0

Subtask #5
21.0 / 21.0

Subtask #6
0.0 / 24.0