oj.uz

Submission #18060

# Submission time Handle Problem Language Result Execution time Memory
18060 2016-01-19T10:55:39 Z comet Wombats (IOI13_wombats) C++
100 / 100
 12160 ms 67528 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]);
		}
	}
}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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 67524 KB Output is correct - 505 tokens
2 Correct 5 ms 67528 KB Output is correct - 505 tokens
3 Correct 91 ms 67520 KB Output is correct - 200005 tokens
4 Correct 2 ms 67524 KB Output is correct - 505 tokens
5 Correct 0 ms 67528 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 0 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 92 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 537 ms 67524 KB Output is correct - 105 tokens
2 Correct 530 ms 67520 KB Output is correct - 105 tokens
3 Correct 547 ms 67520 KB Output is correct - 105 tokens
4 Correct 547 ms 67524 KB Output is correct - 105 tokens
5 Correct 531 ms 67524 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 2663 ms 67524 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 67524 KB Output is correct - 1005 tokens
2 Correct 3 ms 67524 KB Output is correct - 1005 tokens
3 Correct 4 ms 67528 KB Output is correct - 1005 tokens
4 Correct 51 ms 67520 KB Output is correct - 100005 tokens

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 67520 KB Output is correct - 105 tokens
2 Correct 533 ms 67524 KB Output is correct - 105 tokens
3 Correct 536 ms 67528 KB Output is correct - 105 tokens
4 Correct 548 ms 67528 KB Output is correct - 105 tokens
5 Correct 536 ms 67520 KB Output is correct - 105 tokens
6 Correct 0 ms 67524 KB Output is correct - 1005 tokens
7 Correct 4 ms 67520 KB Output is correct - 1005 tokens
8 Correct 3 ms 67524 KB Output is correct - 1005 tokens
9 Correct 20 ms 67524 KB Output is correct - 100005 tokens
10 Correct 0 ms 67524 KB Output is correct - 505 tokens
11 Correct 0 ms 67524 KB Output is correct - 505 tokens
12 Correct 95 ms 67520 KB Output is correct - 200005 tokens
13 Correct 0 ms 67524 KB Output is correct - 505 tokens
14 Correct 3 ms 67528 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 78 ms 67492 KB Output is correct - 200005 tokens
26 Correct 2 ms 67492 KB Output is correct - 405 tokens
27 Correct 2662 ms 67524 KB Output is correct - 105 tokens
28 Correct 3042 ms 67520 KB Output is correct - 50005 tokens
29 Correct 2643 ms 67524 KB Output is correct - 50005 tokens
30 Correct 2634 ms 67528 KB Output is correct - 50005 tokens
31 Correct 3140 ms 67528 KB Output is correct - 200005 tokens
32 Correct 0 ms 67492 KB Output is correct - 8 tokens

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 67520 KB Output is correct - 105 tokens
2 Correct 526 ms 67524 KB Output is correct - 105 tokens
3 Correct 547 ms 67524 KB Output is correct - 105 tokens
4 Correct 549 ms 67524 KB Output is correct - 105 tokens
5 Correct 537 ms 67528 KB Output is correct - 105 tokens
6 Correct 0 ms 67520 KB Output is correct - 1005 tokens
7 Correct 10 ms 67520 KB Output is correct - 1005 tokens
8 Correct 3 ms 67524 KB Output is correct - 1005 tokens
9 Correct 52 ms 67528 KB Output is correct - 100005 tokens
10 Correct 0 ms 67524 KB Output is correct - 505 tokens
11 Correct 0 ms 67520 KB Output is correct - 505 tokens
12 Correct 89 ms 67520 KB Output is correct - 200005 tokens
13 Correct 0 ms 67520 KB Output is correct - 505 tokens
14 Correct 0 ms 67524 KB Output is correct - 505 tokens
15 Correct 2518 ms 67524 KB Output is correct - 11 tokens
16 Correct 12160 ms 67524 KB Output is correct - 200005 tokens
17 Correct 0 ms 67492 KB Output is correct - 6 tokens
18 Correct 0 ms 67492 KB Output is correct - 6 tokens
19 Correct 0 ms 67492 KB Output is correct - 6 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 - 405 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 0 ms 67492 KB Output is correct - 405 tokens
26 Correct 0 ms 67492 KB Output is correct - 366 tokens
27 Correct 89 ms 67492 KB Output is correct - 200005 tokens
28 Correct 0 ms 67492 KB Output is correct - 405 tokens
29 Correct 2662 ms 67528 KB Output is correct - 105 tokens
30 Correct 3032 ms 67520 KB Output is correct - 50005 tokens
31 Correct 11909 ms 67524 KB Output is correct - 100005 tokens
32 Correct 11879 ms 67524 KB Output is correct - 100005 tokens
33 Correct 2611 ms 67528 KB Output is correct - 50005 tokens
34 Correct 10214 ms 67520 KB Output is correct - 100005 tokens
35 Correct 2630 ms 67528 KB Output is correct - 50005 tokens
36 Correct 10353 ms 67528 KB Output is correct - 100005 tokens
37 Correct 3092 ms 67524 KB Output is correct - 200005 tokens
38 Correct 11885 ms 67524 KB Output is correct - 200005 tokens
39 Correct 1 ms 67492 KB Output is correct - 8 tokens
40 Correct 10526 ms 67528 KB Output is correct - 100005 tokens