oj.uz

Submission #805340

# Submission time Handle Problem Language Result Execution time Memory
805340 2023-08-03T15:27:48 Z Antekb Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 48968 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int RMAX=5000, CMAX=500, 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 10 ms 24020 KB Output is correct
2 Correct 11 ms 24096 KB Output is correct
3 Correct 64 ms 25676 KB Output is correct
4 Correct 10 ms 24020 KB Output is correct
5 Correct 10 ms 24020 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 58 ms 1388 KB Output is correct
12 Correct 1 ms 468 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 1216 KB Output is correct
2 Correct 694 ms 1092 KB Output is correct
3 Correct 707 ms 1116 KB Output is correct
4 Correct 714 ms 1104 KB Output is correct
5 Correct 705 ms 1108 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 3531 ms 1108 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28100 KB Output is correct
2 Correct 12 ms 28116 KB Output is correct
3 Correct 12 ms 28128 KB Output is correct
4 Correct 40 ms 28816 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 1108 KB Output is correct
2 Correct 692 ms 1108 KB Output is correct
3 Correct 711 ms 1108 KB Output is correct
4 Correct 712 ms 1116 KB Output is correct
5 Correct 700 ms 1116 KB Output is correct
6 Correct 13 ms 28116 KB Output is correct
7 Correct 14 ms 28156 KB Output is correct
8 Correct 13 ms 28116 KB Output is correct
9 Correct 40 ms 28820 KB Output is correct
10 Correct 10 ms 24020 KB Output is correct
11 Correct 11 ms 24020 KB Output is correct
12 Correct 63 ms 25672 KB Output is correct
13 Correct 10 ms 24020 KB Output is correct
14 Correct 10 ms 24020 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 58 ms 1448 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 3533 ms 1108 KB Output is correct
28 Correct 9767 ms 38612 KB Output is correct
29 Correct 9998 ms 31896 KB Output is correct
30 Correct 9032 ms 31876 KB Output is correct
31 Correct 10133 ms 39560 KB Output is correct
32 Correct 0 ms 340 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 1092 KB Output is correct
2 Correct 694 ms 1104 KB Output is correct
3 Correct 706 ms 1108 KB Output is correct
4 Correct 714 ms 1108 KB Output is correct
5 Correct 709 ms 1100 KB Output is correct
6 Correct 16 ms 28092 KB Output is correct
7 Correct 11 ms 28116 KB Output is correct
8 Correct 11 ms 28008 KB Output is correct
9 Correct 42 ms 28824 KB Output is correct
10 Correct 10 ms 23996 KB Output is correct
11 Correct 10 ms 24020 KB Output is correct
12 Correct 64 ms 25752 KB Output is correct
13 Correct 11 ms 24120 KB Output is correct
14 Correct 10 ms 24068 KB Output is correct
15 Correct 2140 ms 48288 KB Output is correct
16 Execution timed out 20081 ms 48968 KB Time limit exceeded
17 Halted 0 ms 0 KB -