oj.uz

Submission #805334

# Submission time Handle Problem Language Result Execution time Memory
805334 2023-08-03T15:25:23 Z Antekb Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 34028 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int RMAX=5000, CMAX=200, BLOMAX=70;
int H[RMAX][CMAX], V[RMAX][CMAX], R, C, K=200, blo;
int dist[2*BLOMAX][CMAX][CMAX], pocz[BLOMAX], kon[BLOMAX], czy[BLOMAX*2];
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 ans;
}
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);
	}
	/*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;
		}
	}
	/*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;
	}
	/*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 6 ms 12244 KB Output is correct
2 Correct 6 ms 12244 KB Output is correct
3 Correct 58 ms 14028 KB Output is correct
4 Correct 6 ms 12244 KB Output is correct
5 Correct 6 ms 12220 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 304 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 260 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 57 ms 1536 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 696 ms 824 KB Output is correct
2 Correct 702 ms 816 KB Output is correct
3 Correct 707 ms 824 KB Output is correct
4 Correct 714 ms 824 KB Output is correct
5 Correct 703 ms 888 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 3535 ms 820 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 8 ms 16228 KB Output is correct
2 Correct 9 ms 16188 KB Output is correct
3 Correct 11 ms 16212 KB Output is correct
4 Correct 35 ms 17596 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 948 KB Output is correct
2 Correct 699 ms 832 KB Output is correct
3 Correct 708 ms 824 KB Output is correct
4 Correct 714 ms 844 KB Output is correct
5 Correct 713 ms 748 KB Output is correct
6 Correct 9 ms 16216 KB Output is correct
7 Correct 8 ms 16212 KB Output is correct
8 Correct 8 ms 16316 KB Output is correct
9 Correct 36 ms 17624 KB Output is correct
10 Correct 6 ms 12220 KB Output is correct
11 Correct 6 ms 12196 KB Output is correct
12 Correct 58 ms 15052 KB Output is correct
13 Correct 6 ms 12244 KB Output is correct
14 Correct 6 ms 12244 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 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 308 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 67 ms 2692 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 3550 ms 836 KB Output is correct
28 Correct 9831 ms 24336 KB Output is correct
29 Correct 10113 ms 20668 KB Output is correct
30 Correct 9209 ms 20588 KB Output is correct
31 Correct 10214 ms 26016 KB Output is correct
32 Correct 1 ms 308 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 740 KB Output is correct
2 Correct 696 ms 744 KB Output is correct
3 Correct 708 ms 756 KB Output is correct
4 Correct 724 ms 744 KB Output is correct
5 Correct 700 ms 744 KB Output is correct
6 Correct 11 ms 16212 KB Output is correct
7 Correct 8 ms 16212 KB Output is correct
8 Correct 11 ms 16212 KB Output is correct
9 Correct 35 ms 17616 KB Output is correct
10 Correct 8 ms 12232 KB Output is correct
11 Correct 5 ms 12244 KB Output is correct
12 Correct 77 ms 15000 KB Output is correct
13 Correct 6 ms 12220 KB Output is correct
14 Correct 7 ms 12244 KB Output is correct
15 Correct 2190 ms 34028 KB Output is correct
16 Execution timed out 20028 ms 33280 KB Time limit exceeded
17 Halted 0 ms 0 KB -