oj.uz

Submission #18058

# Submission time Handle Problem Language Result Execution time Memory
18058 2016-01-19T10:47:08 Z comet Wombats (IOI13_wombats) C++
76 / 100
 20000 ms 67492 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -