oj.uz

Submission #805548

# Submission time Handle Problem Language Result Execution time Memory
805548 2023-08-03T17:45:42 Z Antekb Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 56828 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int RMAX=5000, CMAX=200, BLOMAX=130;
int H[RMAX][CMAX], V[RMAX][CMAX], R, C, K=43, blo;
int dist[2*BLOMAX][CMAX][CMAX], pocz[BLOMAX], kon[BLOMAX], czy[BLOMAX*2];
int res[CMAX][CMAX];
void get_res(){
	for(int i=0; i<C; i++){
		for(int j=0; j<C; j++){
			res[i][j]=dist[1][i][j];
		}
		for(int j=1; j<C; j++){
			res[i][j]=min(res[i][j], res[i][j-1]+H[R-1][j-1]);
		}
		for(int j=C-2; j>=0; j--){
			res[i][j]=min(res[i][j+1]+H[R-1][j], res[i][j]);
		}
	}
}
int escape(int V1, int V2) {
	/*int ans=dist[1][V1][V2];
	int sum=0;
	for(int i=V2+1; i<C; i++){
		sum+=H[R-1][i-1];
		ans=min(ans, dist[1][V1][i]+sum);
	}
	sum=0;
	for(int i=V2-1; i>=0; i--){
		sum+=H[R-1][i];
		ans=min(ans, dist[1][V1][i]+sum);
	}*/
	//cerr<<ans<<"\n";
	return res[V1][V2];
}
void update(int num){
	int tab[C][C];
	for(int i=0; i<C; i++){
		for(int j=0; j<C; j++){
			tab[i][j]=(1e9)*(i!=j);
		}
	}
	for(int r=pocz[num]; r<=kon[num]; r++){
		for(int i=0; i<C; i++){
			for(int j=1; j<C; j++){
				tab[i][j]=min(tab[i][j], tab[i][j-1]+H[r][j-1]);
			}
			for(int j=C-2; j>=0; j--){
				tab[i][j]=min(tab[i][j+1]+H[r][j], tab[i][j]);
			}
			for(int j=0; j<C; j++){
				tab[i][j]+=V[r][j];
			}
		}
	}
	//cerr<<"\n";
	//cerr<<num<<"\n";
	for(int i=0; i<C; i++){
		for(int j=0; j<C; j++){
			//cerr<<tab[i][j]<<" \n"[j==C-1];
			dist[blo+num][i][j]=tab[i][j];
		}
	}
	//cerr<<"\n";
}
void lacz(int v){
	if(!czy[v])return;
	int l=v+v, r=v+v+1;
	if(!czy[r]){
		for(int i=0; i<C; i++){
			for(int j=0; j<C; j++){
				dist[v][i][j]=dist[l][i][j];
			}
		}
	}
	else{
	for(int i=0; i<C; i++){
		for(int j=0; j<C; j++){
			dist[v][i][j]=1e9;
			for(int k=0; k<C; k++){
				dist[v][i][j]=min(dist[v][i][j], dist[l][i][k]+dist[r][k][j]);
			}
		}
	}
	}
	/*cerr<<"\n";
	cerr<<v<<"a\n";
	cerr<<l<<" "<<r<<"\n";
	for(int i=0; i<C; i++){
		for(int j=0; j<C; j++){
			cerr<<dist[v][i][j]<<" \n"[j==C-1];
		}
	}
	cerr<<"\n";*/

}
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; j++){
			H[i][j]=_H[i][j];
			V[i][j]=_V[i][j];
		}
	}
	for(int i=0; i*K<R-1; i++){
		blo++;
	}
	while(__builtin_popcount(blo)>1)blo++;
	for(int i=0; i*K<R-1; i++){
		pocz[i]=i*K;
		kon[i]=min((i+1)*K-1, R-2);
		update(i);
		czy[i+blo]=1;
	}
	for(int i=blo-1; i>0; i--){
		czy[i]=(czy[i+i]|czy[i+i+1]);
		lacz(i);
	}
	get_res();
	/*for(int i=0; i<C; i++){
		for(int j=0; j<C; j++){
			cerr<<i<<" "<<j<<" "<<escape(i, j)<<"\n";
		}
	}*/
}
void changeH(int P, int Q, int W) {
	H[P][Q]=W;
	if(P!=R-1){
		update(P/K);
		int v=P/K+blo;
		v/=2;
		while(v){
			lacz(v);
			v/=2;
		}
	}
	get_res();
	/*for(int i=0; i<C; i++){
		for(int j=0; j<C; j++){
			cerr<<i<<" "<<j<<" "<<escape(i, j)<<"\n";
		}
	}*/
}

void changeV(int P, int Q, int W) {
	V[P][Q]=W;
	update(P/K);
	int v=P/K+blo;
	v/=2;
	while(v){
		lacz(v);
		v/=2;
	}
	get_res();
	/*for(int i=0; i<C; i++){
		for(int j=0; j<C; j++){
			cerr<<i<<" "<<j<<" "<<escape(i, j)<<"\n";
		}
	}*/
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13012 KB Output is correct
2 Correct 7 ms 13012 KB Output is correct
3 Correct 59 ms 15800 KB Output is correct
4 Correct 6 ms 13012 KB Output is correct
5 Correct 6 ms 12996 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 0 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 432 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 54 ms 2420 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 1308 KB Output is correct
2 Correct 509 ms 1236 KB Output is correct
3 Correct 469 ms 1308 KB Output is correct
4 Correct 486 ms 1312 KB Output is correct
5 Correct 533 ms 1304 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2581 ms 1304 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17212 KB Output is correct
2 Correct 8 ms 17208 KB Output is correct
3 Correct 9 ms 17200 KB Output is correct
4 Correct 38 ms 18484 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 1312 KB Output is correct
2 Correct 529 ms 1296 KB Output is correct
3 Correct 491 ms 1312 KB Output is correct
4 Correct 502 ms 1312 KB Output is correct
5 Correct 512 ms 1312 KB Output is correct
6 Correct 9 ms 17220 KB Output is correct
7 Correct 9 ms 17104 KB Output is correct
8 Correct 8 ms 17232 KB Output is correct
9 Correct 35 ms 18536 KB Output is correct
10 Correct 6 ms 13012 KB Output is correct
11 Correct 6 ms 13116 KB Output is correct
12 Correct 58 ms 15792 KB Output is correct
13 Correct 7 ms 13012 KB Output is correct
14 Correct 5 ms 13112 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 440 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 440 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 66 ms 2748 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2609 ms 1308 KB Output is correct
28 Correct 5446 ms 38160 KB Output is correct
29 Correct 5444 ms 31744 KB Output is correct
30 Correct 4990 ms 31736 KB Output is correct
31 Correct 5790 ms 39180 KB Output is correct
32 Correct 1 ms 340 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 1312 KB Output is correct
2 Correct 583 ms 1300 KB Output is correct
3 Correct 511 ms 1312 KB Output is correct
4 Correct 513 ms 1312 KB Output is correct
5 Correct 523 ms 1308 KB Output is correct
6 Correct 7 ms 17108 KB Output is correct
7 Correct 9 ms 17208 KB Output is correct
8 Correct 8 ms 17216 KB Output is correct
9 Correct 34 ms 18584 KB Output is correct
10 Correct 7 ms 12992 KB Output is correct
11 Correct 5 ms 13092 KB Output is correct
12 Correct 61 ms 15784 KB Output is correct
13 Correct 7 ms 13012 KB Output is correct
14 Correct 7 ms 13116 KB Output is correct
15 Correct 2777 ms 55680 KB Output is correct
16 Execution timed out 20032 ms 56828 KB Time limit exceeded
17 Halted 0 ms 0 KB -