oj.uz

Submission #18055

# Submission time Handle Problem Language Result Execution time Memory
18055 2016-01-19T10:23:39 Z comet Wombats (IOI13_wombats) C++
12 / 100
 780 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]);
		}
	}
}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 k=0;k<C;k++){
				tree[k].dp[i][j]=min(tree[k].dp[i][j],
					tree[LL].dp[i][k]+V[y][k]+tree[RR].dp[k][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+1,0);
}

int escape(int v1, int v2) {

	return tree[0].dp[v1][v2];
}

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 67492 KB Output isn't correct - 1st words differ - expected: '0', found: '1000000000'
2 Halted 0 ms 0 KB -

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 2 ms 67492 KB Output is correct - 366 tokens
9 Correct 2 ms 67492 KB Output is correct - 405 tokens
10 Correct 0 ms 67492 KB Output is correct - 366 tokens
11 Correct 83 ms 67492 KB Output is correct - 200005 tokens
12 Correct 0 ms 67492 KB Output is correct - 405 tokens

Subtask #3
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 767 ms 67492 KB Output isn't correct - 1st words differ - expected: '34137', found: '1767'
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 67492 KB Output isn't correct - 1st words differ - expected: '2116460', found: '1000000000'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 780 ms 67492 KB Output isn't correct - 1st words differ - expected: '34137', found: '1767'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 768 ms 67492 KB Output isn't correct - 1st words differ - expected: '34137', found: '1767'
2 Halted 0 ms 0 KB -