oj.uz

Submission #2485

# Submission time Handle Problem Language Result Execution time Memory
2485 2013-07-22T12:49:16 Z kriii Wombats (IOI13_wombats) C++
76 / 100
 20000 ms 56672 KB 
#include "wombats.h"
#define group_size 50

const int NON = 0x0fffffff;
const int Z = 128;
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 4 ms 56672 KB Output is correct
2 Correct 4 ms 56672 KB Output is correct
3 Correct 94 ms 56672 KB Output is correct
4 Correct 1 ms 56672 KB Output is correct
5 Correct 0 ms 56672 KB Output is correct
6 Correct 0 ms 56672 KB Output is correct
7 Correct 0 ms 56672 KB Output is correct
8 Correct 0 ms 56672 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 56672 KB Output is correct
2 Correct 0 ms 56672 KB Output is correct
3 Correct 0 ms 56672 KB Output is correct
4 Correct 6 ms 56672 KB Output is correct
5 Correct 5 ms 56672 KB Output is correct
6 Correct 4 ms 56672 KB Output is correct
7 Correct 7 ms 56672 KB Output is correct
8 Correct 4 ms 56672 KB Output is correct
9 Correct 4 ms 56672 KB Output is correct
10 Correct 2 ms 56672 KB Output is correct
11 Correct 75 ms 56672 KB Output is correct
12 Correct 4 ms 56672 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1027 ms 56672 KB Output is correct
2 Correct 1038 ms 56672 KB Output is correct
3 Correct 903 ms 56672 KB Output is correct
4 Correct 1081 ms 56672 KB Output is correct
5 Correct 890 ms 56672 KB Output is correct
6 Correct 0 ms 56672 KB Output is correct
7 Correct 0 ms 56672 KB Output is correct
8 Correct 0 ms 56672 KB Output is correct
9 Correct 4761 ms 56672 KB Output is correct
10 Correct 0 ms 56672 KB Output is correct

Subtask #4
18.0 / 18.0

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

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 871 ms 56672 KB Output is correct
2 Correct 880 ms 56672 KB Output is correct
3 Correct 900 ms 56672 KB Output is correct
4 Correct 1088 ms 56672 KB Output is correct
5 Correct 892 ms 56672 KB Output is correct
6 Correct 3 ms 56672 KB Output is correct
7 Correct 3 ms 56672 KB Output is correct
8 Correct 5 ms 56672 KB Output is correct
9 Correct 43 ms 56672 KB Output is correct
10 Correct 0 ms 56672 KB Output is correct
11 Correct 2 ms 56672 KB Output is correct
12 Correct 80 ms 56672 KB Output is correct
13 Correct 2 ms 56672 KB Output is correct
14 Correct 0 ms 56672 KB Output is correct
15 Correct 0 ms 56672 KB Output is correct
16 Correct 0 ms 56672 KB Output is correct
17 Correct 0 ms 56672 KB Output is correct
18 Correct 5 ms 56672 KB Output is correct
19 Correct 4 ms 56672 KB Output is correct
20 Correct 5 ms 56672 KB Output is correct
21 Correct 6 ms 56672 KB Output is correct
22 Correct 4 ms 56672 KB Output is correct
23 Correct 4 ms 56672 KB Output is correct
24 Correct 3 ms 56672 KB Output is correct
25 Correct 101 ms 56672 KB Output is correct
26 Correct 5 ms 56672 KB Output is correct
27 Correct 4767 ms 56672 KB Output is correct
28 Correct 5767 ms 56672 KB Output is correct
29 Correct 5291 ms 56672 KB Output is correct
30 Correct 5676 ms 56672 KB Output is correct
31 Correct 5803 ms 56672 KB Output is correct
32 Correct 0 ms 56672 KB Output is correct

Subtask #6
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 877 ms 56672 KB Output is correct
2 Correct 894 ms 56672 KB Output is correct
3 Correct 1054 ms 56672 KB Output is correct
4 Correct 1059 ms 56672 KB Output is correct
5 Correct 896 ms 56672 KB Output is correct
6 Correct 6 ms 56672 KB Output is correct
7 Correct 5 ms 56672 KB Output is correct
8 Correct 4 ms 56672 KB Output is correct
9 Correct 44 ms 56672 KB Output is correct
10 Correct 2 ms 56672 KB Output is correct
11 Correct 1 ms 56672 KB Output is correct
12 Correct 82 ms 56672 KB Output is correct
13 Correct 2 ms 56672 KB Output is correct
14 Correct 4 ms 56672 KB Output is correct
15 Correct 3658 ms 56672 KB Output is correct
16 Correct 19414 ms 56672 KB Output is correct
17 Correct 0 ms 56672 KB Output is correct
18 Correct 0 ms 56672 KB Output is correct
19 Correct 0 ms 56672 KB Output is correct
20 Correct 5 ms 56672 KB Output is correct
21 Correct 3 ms 56672 KB Output is correct
22 Correct 4 ms 56672 KB Output is correct
23 Correct 3 ms 56672 KB Output is correct
24 Correct 3 ms 56672 KB Output is correct
25 Correct 3 ms 56672 KB Output is correct
26 Correct 3 ms 56672 KB Output is correct
27 Correct 79 ms 56672 KB Output is correct
28 Correct 6 ms 56672 KB Output is correct
29 Correct 4018 ms 56672 KB Output is correct
30 Correct 4904 ms 56672 KB Output is correct
31 Execution timed out 20000 ms 0 KB Program timed out
32 Halted 0 ms 0 KB -