oj.uz

Submission #805349

# Submission time Handle Problem Language Result Execution time Memory
805349 2023-08-03T15:35:10 Z Antekb Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 18692 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=675, 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 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 58 ms 13600 KB Output is correct
4 Correct 6 ms 12116 KB Output is correct
5 Correct 7 ms 12044 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 212 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 0 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 340 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 56 ms 1288 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 700 ms 744 KB Output is correct
2 Correct 697 ms 744 KB Output is correct
3 Correct 720 ms 740 KB Output is correct
4 Correct 724 ms 744 KB Output is correct
5 Correct 711 ms 748 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3554 ms 752 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 9 ms 15980 KB Output is correct
2 Correct 10 ms 15940 KB Output is correct
3 Correct 10 ms 15956 KB Output is correct
4 Correct 37 ms 16748 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 744 KB Output is correct
2 Correct 706 ms 744 KB Output is correct
3 Correct 716 ms 744 KB Output is correct
4 Correct 722 ms 744 KB Output is correct
5 Correct 705 ms 744 KB Output is correct
6 Correct 10 ms 15956 KB Output is correct
7 Correct 11 ms 16036 KB Output is correct
8 Correct 11 ms 16044 KB Output is correct
9 Correct 38 ms 16716 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 59 ms 13712 KB Output is correct
13 Correct 6 ms 12116 KB Output is correct
14 Correct 6 ms 12116 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 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 340 KB Output is correct
21 Correct 1 ms 372 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 57 ms 1376 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 3549 ms 764 KB Output is correct
28 Execution timed out 20073 ms 17488 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 744 KB Output is correct
2 Correct 694 ms 760 KB Output is correct
3 Correct 709 ms 760 KB Output is correct
4 Correct 714 ms 748 KB Output is correct
5 Correct 702 ms 724 KB Output is correct
6 Correct 12 ms 15956 KB Output is correct
7 Correct 12 ms 16044 KB Output is correct
8 Correct 11 ms 15956 KB Output is correct
9 Correct 38 ms 16772 KB Output is correct
10 Correct 6 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 59 ms 13632 KB Output is correct
13 Correct 6 ms 12116 KB Output is correct
14 Correct 6 ms 12116 KB Output is correct
15 Correct 2463 ms 18436 KB Output is correct
16 Execution timed out 20027 ms 18692 KB Time limit exceeded
17 Halted 0 ms 0 KB -