oj.uz

Submission #2483

# Submission time Handle Problem Language Result Execution time Memory
2483 2013-07-22T12:42:06 Z kriii Wombats (IOI13_wombats) C++
28 / 100
 7183 ms 36672 KB 
#include "wombats.h"
#define group_size 80

const int NON = 0x0fffffff;
const int Z = 64;
int N, M, G, Start[30], End[30];

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);

	make();
}

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

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

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

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 36672 KB Output is correct
2 Incorrect 1 ms 36672 KB Output isn't correct - 정답과 다른 결과를 출력하여 중간에 강제종료되었습니다.
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 708 ms 36672 KB Output is correct
2 Correct 1428 ms 36672 KB Output is correct
3 Correct 1343 ms 36672 KB Output is correct
4 Correct 1114 ms 36672 KB Output is correct
5 Correct 1249 ms 36672 KB Output is correct
6 Correct 0 ms 36672 KB Output is correct
7 Correct 0 ms 36672 KB Output is correct
8 Correct 0 ms 36672 KB Output is correct
9 Correct 7183 ms 36672 KB Output is correct
10 Correct 0 ms 36672 KB Output is correct

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 36672 KB Output isn't correct - 정답과 다른 결과를 출력하여 중간에 강제종료되었습니다.
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 702 ms 36672 KB Output is correct
2 Correct 1499 ms 36672 KB Output is correct
3 Correct 1115 ms 36672 KB Output is correct
4 Correct 1294 ms 36672 KB Output is correct
5 Correct 1508 ms 36672 KB Output is correct
6 Incorrect 9 ms 36672 KB Output isn't correct - 정답과 다른 결과를 출력하여 중간에 강제종료되었습니다.
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 841 ms 36672 KB Output is correct
2 Correct 1245 ms 36672 KB Output is correct
3 Correct 1329 ms 36672 KB Output is correct
4 Correct 1124 ms 36672 KB Output is correct
5 Correct 1446 ms 36672 KB Output is correct
6 Incorrect 9 ms 36672 KB Output isn't correct - 정답과 다른 결과를 출력하여 중간에 강제종료되었습니다.
7 Halted 0 ms 0 KB -