답안 #4613 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4613	2013-11-10T11:23:31 Z	cki86201	웜뱃 (IOI13_wombats)	C++	100 / 100	7476 ms	177660 KB

wombats

#include "wombats.h"
#include<stdlib.h>
#include<queue>
#include<vector>
#include<functional>
#include<string.h>
using namespace std;

#define X first
#define Y second

typedef pair<int,int> P;
typedef pair<int,P> Pi;
const int id = 512;
const int inf = 1e9;
const int bz = 10;

int H[5000][200],V[5000][200];
int T[1030][200][200];
int tmp[bz+1][200];
int R,C;

void upd(int x,int y)
{
	int i,j;
	memset(tmp[0],0,sizeof(tmp[0]));
	for(i=x-1;i>=0;i--)tmp[0][i]=tmp[0][i+1]+H[bz*y][i];
	for(i=x+1;i<C;i++)tmp[0][i] =tmp[0][i-1]+H[bz*y][i-1];
	for(i=1;i<=bz && bz*y+i<R;i++){
		for(j=0;j<C;j++)tmp[i][j]=tmp[i-1][j]+V[bz*y+i-1][j];
		for(j=C-2;j>=0;j--)tmp[i][j]=min(tmp[i][j],tmp[i][j+1]+H[bz*y+i][j]);
		for(j=1;j<C;j++)tmp[i][j]=min(tmp[i][j],tmp[i][j-1]+H[bz*y+i][j-1]);
	}
	for(j=0;j<C;j++)T[id+y][x][j]=tmp[i-1][j];
}

void Union(int t)
{
	int i,j,k;
	int sk[200];
	for(i=0;i<C;i++)sk[i]=0;
	for(i=0;i<C;i++)for(j=0;j<C;j++)T[t][i][j]=inf;
	for(i=C-1;i>=-C+1;i--){
		for(j=min(C-1,C-i-1);j>=0&&j+i>=0;j--){
			int s=j==max(0,-i)?0:sk[j-1];
			int d=j==min(C-1,C-i-1)?C-1:sk[j];
			for(k=s;k<=d;k++){
				if(T[t][j][j+i] > T[t<<1][j][k] + T[t<<1|1][k][j+i]){
					T[t][j][j+i]=T[t<<1][j][k] + T[t<<1|1][k][j+i];
					sk[j]=k;
				}
			}
		}
	}
	for(i=0;i<C;i++)if(T[t][i][i]==inf)T[t][i][i]=0;
}

void init(int R, int C, int H_[5000][200], int V_[5000][200]){
	int i,j;
	for(i=0;i<R;i++)for(j=0;j<C-1;j++)H[i][j]=H_[i][j];
	for(i=0;i<R-1;i++)for(j=0;j<C;j++)V[i][j]=V_[i][j];
	::R=R;
	::C=C;
	for(i=0;i<C;i++){
		for(j=0;bz*j<R;j++){
			upd(i,j);
		}
		for(;j<id;j++){
			for(int u=0;u<C;u++)T[id+j][i][u]=i==u?0:inf;
		}
	}
	for(i=id-1;i;i--)Union(i);
}

void changeH(int P, int Q, int W){
	H[P][Q]=W;
	int i,r=P/bz;
	for(i=0;i<C;i++)upd(i,r);
	if(P%bz == 0 && P){
		for(i=0;i<C;i++)upd(i,r-1);
		int t=(r+id-1)/2;
		while(t){Union(t);t>>=1;}
	}
	r+=id;
	r>>=1;
	while(r){
		Union(r);
		r>>=1;
	}
}

void changeV(int P, int Q, int W) {
    V[P][Q]=W;
    int i,r=P/bz;
	for(i=0;i<C;i++)upd(i,r);
	r+=id;
	r>>=1;
	while(r){
		Union(r);
		r>>=1;
	}
}

int escape(int V1, int V2){
	return T[1][V1][V2];
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	177660 KB	Output is correct
2	Correct	4 ms	177660 KB	Output is correct
3	Correct	84 ms	177660 KB	Output is correct
4	Correct	0 ms	177660 KB	Output is correct
5	Correct	0 ms	177660 KB	Output is correct
6	Correct	0 ms	177660 KB	Output is correct
7	Correct	0 ms	177660 KB	Output is correct
8	Correct	0 ms	177660 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	177660 KB	Output is correct
2	Correct	0 ms	177660 KB	Output is correct
3	Correct	0 ms	177660 KB	Output is correct
4	Correct	4 ms	177660 KB	Output is correct
5	Correct	4 ms	177660 KB	Output is correct
6	Correct	4 ms	177660 KB	Output is correct
7	Correct	4 ms	177660 KB	Output is correct
8	Correct	12 ms	177660 KB	Output is correct
9	Correct	0 ms	177660 KB	Output is correct
10	Correct	4 ms	177660 KB	Output is correct
11	Correct	88 ms	177660 KB	Output is correct
12	Correct	8 ms	177660 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	296 ms	177660 KB	Output is correct
2	Correct	288 ms	177660 KB	Output is correct
3	Correct	336 ms	177660 KB	Output is correct
4	Correct	304 ms	177660 KB	Output is correct
5	Correct	308 ms	177660 KB	Output is correct
6	Correct	0 ms	177660 KB	Output is correct
7	Correct	0 ms	177660 KB	Output is correct
8	Correct	0 ms	177660 KB	Output is correct
9	Correct	1192 ms	177660 KB	Output is correct
10	Correct	0 ms	177660 KB	Output is correct

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	177660 KB	Output is correct
2	Correct	0 ms	177660 KB	Output is correct
3	Correct	8 ms	177660 KB	Output is correct
4	Correct	48 ms	177660 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	292 ms	177660 KB	Output is correct
2	Correct	280 ms	177660 KB	Output is correct
3	Correct	328 ms	177660 KB	Output is correct
4	Correct	312 ms	177660 KB	Output is correct
5	Correct	292 ms	177660 KB	Output is correct
6	Correct	0 ms	177660 KB	Output is correct
7	Correct	0 ms	177660 KB	Output is correct
8	Correct	0 ms	177660 KB	Output is correct
9	Correct	48 ms	177660 KB	Output is correct
10	Correct	0 ms	177660 KB	Output is correct
11	Correct	0 ms	177660 KB	Output is correct
12	Correct	84 ms	177660 KB	Output is correct
13	Correct	4 ms	177660 KB	Output is correct
14	Correct	8 ms	177660 KB	Output is correct
15	Correct	0 ms	177660 KB	Output is correct
16	Correct	0 ms	177660 KB	Output is correct
17	Correct	0 ms	177660 KB	Output is correct
18	Correct	8 ms	177660 KB	Output is correct
19	Correct	4 ms	177660 KB	Output is correct
20	Correct	8 ms	177660 KB	Output is correct
21	Correct	8 ms	177660 KB	Output is correct
22	Correct	8 ms	177660 KB	Output is correct
23	Correct	8 ms	177660 KB	Output is correct
24	Correct	4 ms	177660 KB	Output is correct
25	Correct	88 ms	177660 KB	Output is correct
26	Correct	4 ms	177660 KB	Output is correct
27	Correct	1208 ms	177660 KB	Output is correct
28	Correct	1924 ms	177660 KB	Output is correct
29	Correct	1856 ms	177660 KB	Output is correct
30	Correct	1900 ms	177660 KB	Output is correct
31	Correct	1956 ms	177660 KB	Output is correct
32	Correct	0 ms	177660 KB	Output is correct

Subtask #6
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	328 ms	177660 KB	Output is correct
2	Correct	288 ms	177660 KB	Output is correct
3	Correct	344 ms	177660 KB	Output is correct
4	Correct	312 ms	177660 KB	Output is correct
5	Correct	296 ms	177660 KB	Output is correct
6	Correct	4 ms	177660 KB	Output is correct
7	Correct	4 ms	177660 KB	Output is correct
8	Correct	0 ms	177660 KB	Output is correct
9	Correct	44 ms	177660 KB	Output is correct
10	Correct	0 ms	177660 KB	Output is correct
11	Correct	8 ms	177660 KB	Output is correct
12	Correct	88 ms	177660 KB	Output is correct
13	Correct	0 ms	177660 KB	Output is correct
14	Correct	4 ms	177660 KB	Output is correct
15	Correct	2788 ms	177660 KB	Output is correct
16	Correct	7476 ms	177660 KB	Output is correct
17	Correct	0 ms	177660 KB	Output is correct
18	Correct	0 ms	177660 KB	Output is correct
19	Correct	0 ms	177660 KB	Output is correct
20	Correct	0 ms	177660 KB	Output is correct
21	Correct	8 ms	177660 KB	Output is correct
22	Correct	4 ms	177660 KB	Output is correct
23	Correct	0 ms	177660 KB	Output is correct
24	Correct	4 ms	177660 KB	Output is correct
25	Correct	8 ms	177660 KB	Output is correct
26	Correct	4 ms	177660 KB	Output is correct
27	Correct	96 ms	177660 KB	Output is correct
28	Correct	4 ms	177660 KB	Output is correct
29	Correct	1192 ms	177660 KB	Output is correct
30	Correct	1924 ms	177660 KB	Output is correct
31	Correct	7288 ms	177660 KB	Output is correct
32	Correct	7340 ms	177660 KB	Output is correct
33	Correct	1860 ms	177660 KB	Output is correct
34	Correct	7092 ms	177660 KB	Output is correct
35	Correct	1908 ms	177660 KB	Output is correct
36	Correct	7120 ms	177660 KB	Output is correct
37	Correct	1952 ms	177660 KB	Output is correct
38	Correct	7232 ms	177660 KB	Output is correct
39	Correct	4 ms	177660 KB	Output is correct
40	Correct	7364 ms	177660 KB	Output is correct

답안 #4613

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 24.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
24.0 / 24.0