oj.uz

Submission #805344

# Submission time Handle Problem Language Result Execution time Memory
805344 2023-08-03T15:29:56 Z Antekb Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 59100 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int RMAX=5000, CMAX=625, 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 11 ms 29012 KB Output is correct
2 Correct 12 ms 29012 KB Output is correct
3 Correct 68 ms 30628 KB Output is correct
4 Correct 11 ms 29036 KB Output is correct
5 Correct 11 ms 29012 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 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 3 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 424 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 1492 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 690 ms 1368 KB Output is correct
2 Correct 693 ms 1236 KB Output is correct
3 Correct 707 ms 1260 KB Output is correct
4 Correct 716 ms 1356 KB Output is correct
5 Correct 700 ms 1356 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 3524 ms 1244 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 13 ms 32980 KB Output is correct
2 Correct 14 ms 32980 KB Output is correct
3 Correct 13 ms 32980 KB Output is correct
4 Correct 41 ms 33860 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 691 ms 1252 KB Output is correct
2 Correct 696 ms 1240 KB Output is correct
3 Correct 707 ms 1356 KB Output is correct
4 Correct 713 ms 1248 KB Output is correct
5 Correct 699 ms 1248 KB Output is correct
6 Correct 13 ms 32980 KB Output is correct
7 Correct 13 ms 33052 KB Output is correct
8 Correct 13 ms 32980 KB Output is correct
9 Correct 42 ms 33872 KB Output is correct
10 Correct 11 ms 29012 KB Output is correct
11 Correct 11 ms 28976 KB Output is correct
12 Correct 64 ms 30612 KB Output is correct
13 Correct 11 ms 29012 KB Output is correct
14 Correct 11 ms 29012 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 63 ms 1552 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 3531 ms 1268 KB Output is correct
28 Correct 9770 ms 45988 KB Output is correct
29 Correct 10009 ms 38252 KB Output is correct
30 Correct 9060 ms 38160 KB Output is correct
31 Correct 10180 ms 47172 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 694 ms 1260 KB Output is correct
2 Correct 691 ms 1244 KB Output is correct
3 Correct 708 ms 1248 KB Output is correct
4 Correct 713 ms 1244 KB Output is correct
5 Correct 699 ms 1240 KB Output is correct
6 Correct 14 ms 32980 KB Output is correct
7 Correct 14 ms 32980 KB Output is correct
8 Correct 14 ms 33068 KB Output is correct
9 Correct 48 ms 33788 KB Output is correct
10 Correct 12 ms 29048 KB Output is correct
11 Correct 13 ms 29036 KB Output is correct
12 Correct 66 ms 30564 KB Output is correct
13 Correct 11 ms 28952 KB Output is correct
14 Correct 11 ms 29012 KB Output is correct
15 Correct 2139 ms 58372 KB Output is correct
16 Execution timed out 20016 ms 59100 KB Time limit exceeded
17 Halted 0 ms 0 KB -