oj.uz

Submission #2486

# Submission time Handle Problem Language Result Execution time Memory
2486 2013-07-22T12:51:32 Z kriii Wombats (IOI13_wombats) C++
100 / 100
 12266 ms 176676 KB 
#include "wombats.h"
#define group_size 10

const int NON = 0x0fffffff;
const int Z = 512;
int N, M, G, Start[Z], End[Z], MADE;
int ANS[200][200],GO[Z*2][200][200];
int NOW[200],LEFT[200],RIGHT[200];
int HH[5000][200],VV[5000][200];

inline int min(int a, int b){return a < b ? a : b;}

void going(int i)
{
	int j;

	for (j=0;j<M;j++) LEFT[j] = RIGHT[j] = NOW[j];
	for (j=1;j<M;j++){
		if (LEFT[j-1] == NON) continue;
		LEFT[j] = min(LEFT[j],LEFT[j-1]+HH[i][j-1]);
	}
	for (j=M-2;j>=0;j--){
		if (RIGHT[j+1] == NON) continue;
		RIGHT[j] = min(RIGHT[j],RIGHT[j+1]+HH[i][j]);
	}
	for (j=0;j<M;j++){
		NOW[j] = min(NOW[j],LEFT[j]);
		NOW[j] = min(NOW[j],RIGHT[j]);
	}
}

void make()
{
	int i,j;

	for (i=0;i<M;i++){
		for (j=0;j<M;j++) NOW[j] = GO[1][i][j];
		going(N-1);
		for (j=0;j<M;j++) ANS[i][j] = NOW[j];
	}
}

void modify(int g)
{
	int i,j,k,x=g+Z,s,p;

	if (g >= G){
		for (i=0;i<M;i++){
			for (j=0;j<M;j++){
				GO[x][i][j] = i == j ? 0 : NON;
			}
		}
	}
	else{
		for (i=0;i<M;i++){
			for (j=0;j<M;j++) NOW[j] = NON;
			NOW[i] = 0;
			for (k=Start[g];k<End[g];k++){
				going(k);
				for (j=0;j<M;j++) NOW[j] += VV[k][j];
			}
			for (j=0;j<M;j++) GO[x][i][j] = NOW[j];
		}
	}

	x /= 2;
	while (x){
		NOW[0] = 0; NOW[1] = M-1;
		for (i=M-1;i>=0;i--){
			for (j=M-1;j>=i;j--){
				s = NON; p = NOW[j-i];
				for (k=NOW[j-i];k<=NOW[j-i+1];k++){
					int &a = GO[x*2][j-i][k];
					int &b = GO[x*2+1][k][j];
					if (s >= a + b){
						s = a + b;
						p = k;
					}
				}
				GO[x][j-i][j] = s;
				NOW[j-i+1] = p;
			}
			NOW[M-i+1] = M-1;
		}

		NOW[0] = 0; NOW[1] = M-1;
		for (i=M-1;i>=0;i--){
			for (j=M-1;j>=i;j--){
				s = NON; p = NOW[j-i];
				for (k=NOW[j-i];k<=NOW[j-i+1];k++){
					int &a = GO[x*2][j][k];
					int &b = GO[x*2+1][k][j-i];
					if (s >= a + b){
						s = a + b;
						p = k;
					}
				}
				GO[x][j][j-i] = s;
				NOW[j-i+1] = p;
			}
			NOW[M-i+1] = M-1;
		}

		x /= 2;
	}
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	N = R; M = C;
	G = (R + group_size - 1) / group_size; int i,j;
	for (i=0;i<G;i++){
		Start[i] = i * group_size;
		End[i] = (i + 1) * group_size;
	}
	if (End[G-1] >= R) End[G-1] = R-1;
	if (Start[G-1] == End[G-1]) G--;

	for (i=0;i<R;i++) for (j=0;j<C-1;j++) HH[i][j] = H[i][j];
	for (i=0;i<R-1;i++) for (j=0;j<C;j++) VV[i][j] = V[i][j];
	for (i=0;i<Z;i++) modify(i);

	MADE = 0;
}

void changeH(int P, int Q, int W) {
	HH[P][Q] = W;
	modify(P/group_size);
	MADE = 0;
}

void changeV(int P, int Q, int W) {
	VV[P][Q] = W;
	modify(P/group_size);
	MADE = 0;
}

int escape(int V1, int V2) {
	if (MADE == 0){
		make(); MADE = 1;
	}
	return ANS[V1][V2];
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 176676 KB Output is correct
2 Correct 2 ms 176676 KB Output is correct
3 Correct 83 ms 176676 KB Output is correct
4 Correct 2 ms 176676 KB Output is correct
5 Correct 0 ms 176676 KB Output is correct
6 Correct 2 ms 176676 KB Output is correct
7 Correct 0 ms 176676 KB Output is correct
8 Correct 0 ms 176676 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 176676 KB Output is correct
2 Correct 0 ms 176676 KB Output is correct
3 Correct 0 ms 176676 KB Output is correct
4 Correct 23 ms 176676 KB Output is correct
5 Correct 23 ms 176676 KB Output is correct
6 Correct 23 ms 176676 KB Output is correct
7 Correct 31 ms 176676 KB Output is correct
8 Correct 19 ms 176676 KB Output is correct
9 Correct 28 ms 176676 KB Output is correct
10 Correct 25 ms 176676 KB Output is correct
11 Correct 122 ms 176676 KB Output is correct
12 Correct 23 ms 176676 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 176676 KB Output is correct
2 Correct 783 ms 176676 KB Output is correct
3 Correct 820 ms 176676 KB Output is correct
4 Correct 825 ms 176676 KB Output is correct
5 Correct 808 ms 176676 KB Output is correct
6 Correct 0 ms 176676 KB Output is correct
7 Correct 0 ms 176676 KB Output is correct
8 Correct 0 ms 176676 KB Output is correct
9 Correct 2000 ms 176676 KB Output is correct
10 Correct 0 ms 176676 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 176676 KB Output is correct
2 Correct 3 ms 176676 KB Output is correct
3 Correct 5 ms 176676 KB Output is correct
4 Correct 47 ms 176676 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 921 ms 176676 KB Output is correct
2 Correct 788 ms 176676 KB Output is correct
3 Correct 970 ms 176676 KB Output is correct
4 Correct 827 ms 176676 KB Output is correct
5 Correct 976 ms 176676 KB Output is correct
6 Correct 5 ms 176676 KB Output is correct
7 Correct 7 ms 176676 KB Output is correct
8 Correct 7 ms 176676 KB Output is correct
9 Correct 60 ms 176676 KB Output is correct
10 Correct 2 ms 176676 KB Output is correct
11 Correct 3 ms 176676 KB Output is correct
12 Correct 102 ms 176676 KB Output is correct
13 Correct 0 ms 176676 KB Output is correct
14 Correct 0 ms 176676 KB Output is correct
15 Correct 1 ms 176676 KB Output is correct
16 Correct 1 ms 176676 KB Output is correct
17 Correct 0 ms 176676 KB Output is correct
18 Correct 31 ms 176676 KB Output is correct
19 Correct 18 ms 176676 KB Output is correct
20 Correct 31 ms 176676 KB Output is correct
21 Correct 23 ms 176676 KB Output is correct
22 Correct 27 ms 176676 KB Output is correct
23 Correct 22 ms 176676 KB Output is correct
24 Correct 27 ms 176676 KB Output is correct
25 Correct 103 ms 176676 KB Output is correct
26 Correct 28 ms 176676 KB Output is correct
27 Correct 2127 ms 176676 KB Output is correct
28 Correct 2934 ms 176676 KB Output is correct
29 Correct 3191 ms 176676 KB Output is correct
30 Correct 2732 ms 176676 KB Output is correct
31 Correct 2780 ms 176676 KB Output is correct
32 Correct 1 ms 176676 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 176676 KB Output is correct
2 Correct 784 ms 176676 KB Output is correct
3 Correct 833 ms 176676 KB Output is correct
4 Correct 837 ms 176676 KB Output is correct
5 Correct 814 ms 176676 KB Output is correct
6 Correct 3 ms 176676 KB Output is correct
7 Correct 4 ms 176676 KB Output is correct
8 Correct 6 ms 176676 KB Output is correct
9 Correct 54 ms 176676 KB Output is correct
10 Correct 2 ms 176676 KB Output is correct
11 Correct 2 ms 176676 KB Output is correct
12 Correct 86 ms 176676 KB Output is correct
13 Correct 3 ms 176676 KB Output is correct
14 Correct 0 ms 176676 KB Output is correct
15 Correct 5199 ms 176676 KB Output is correct
16 Correct 10728 ms 176676 KB Output is correct
17 Correct 1 ms 176676 KB Output is correct
18 Correct 0 ms 176676 KB Output is correct
19 Correct 0 ms 176676 KB Output is correct
20 Correct 30 ms 176676 KB Output is correct
21 Correct 29 ms 176676 KB Output is correct
22 Correct 22 ms 176676 KB Output is correct
23 Correct 22 ms 176676 KB Output is correct
24 Correct 21 ms 176676 KB Output is correct
25 Correct 26 ms 176676 KB Output is correct
26 Correct 22 ms 176676 KB Output is correct
27 Correct 112 ms 176676 KB Output is correct
28 Correct 32 ms 176676 KB Output is correct
29 Correct 2103 ms 176676 KB Output is correct
30 Correct 3186 ms 176676 KB Output is correct
31 Correct 12266 ms 176676 KB Output is correct
32 Correct 11531 ms 176676 KB Output is correct
33 Correct 3245 ms 176676 KB Output is correct
34 Correct 11184 ms 176676 KB Output is correct
35 Correct 2735 ms 176676 KB Output is correct
36 Correct 11235 ms 176676 KB Output is correct
37 Correct 2993 ms 176676 KB Output is correct
38 Correct 11292 ms 176676 KB Output is correct
39 Correct 0 ms 176676 KB Output is correct
40 Correct 11456 ms 176676 KB Output is correct