oj.uz

Submission #1037454

# Submission time Handle Problem Language Result Execution time Memory
1037454 2024-07-28T22:37:42 Z aaaaaarroz Soccer Stadium (IOI23_soccer) C++17
40.5 / 100
 4500 ms 39504 KB 
#include <bits/stdc++.h>
using namespace std;
bool limites(int N, int i, int j){
	return i>=0&&i<N&&j>=0&&j<N;
}
bool comprobar(int N, vector<vector<int>> F){
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(F[i][j]==1){
				continue;
			}
			priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>>cola;
			int dx[]={1,0,-1,0};
			int dy[]={0,1,0,-1};
			vector<vector<int>>dist(N,vector<int>(N,INT_MAX));
			dist[i][j]=0;
			cola.push({0,i,j});
			while(!cola.empty()){
				auto[d,x,y]=cola.top();
				cola.pop();
				for(int dir=0;dir<4;dir++){
					int posi=x+dx[dir];
					int posj=y+dy[dir];
					while(true){
						if(!limites(N,posi,posj)||F[posi][posj]==1)break;
						if((d+1)<dist[posi][posj]){
							dist[posi][posj]=d+1;
							cola.push({dist[posi][posj],posi,posj});
						}
						posi+=dx[dir];
						posj+=dy[dir];
					}
				}
			}
			for(int x=0;x<N;x++){
				for(int y=0;y<N;y++){
					if(F[x][y]==0&&(dist[x][y]>=3||dist[x][y]==-1)){
						return false;
					}
				}
			}
		}
	}
	return true;
}
int biggest_stadium(int N, vector<vector<int>> F){
	int si_hay_arbol=0;
	pair<int,int>arbol;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(F[i][j]==0){
				continue;
			}
			else{
				arbol={i,j};
				si_hay_arbol++;
			}
		}
	}
	if(!si_hay_arbol){
		return N*N;
	}
	else if(si_hay_arbol==1){
		int a=((arbol.first+1)*(arbol.second+1))+min((arbol.first+1),(arbol.second+1));
		int b=(((arbol.first+1)*(N-arbol.second))+min((arbol.first+1),(N-arbol.second)));
		int c=(((N-arbol.first)*(arbol.second+1))+min((N-arbol.first),(arbol.second+1)));
		int d=(((N-arbol.first)*(N-arbol.second))+min((N-arbol.first),(N-arbol.second)));
		int e=((arbol.first+1)*(arbol.second+1));
		int f=(((arbol.first+1)*(N-arbol.second)));
		int g=(((N-arbol.first)*(arbol.second+1)));
		int h=(((N-arbol.first)*(N-arbol.second)));
		int max_rectangle=min(min(a,b),min(c,d));
		max_rectangle=min(max_rectangle,min(min(e,f),min(g,h)));
		return (N*N)-max_rectangle;
	}
	else if(N<=7){
		int n = N;
		vector<vector<int>> a = F, next(n, vector<int>(n)), sum(n, vector<int>(n));
		function<int(int, int, int, int)> summ = [&] (int l, int r, int x, int y) {
			long long ans = sum[y][r];
			if (x - 1 >= 0) ans -= sum[x - 1][r];
			if (l - 1 >= 0) ans -= sum[y][l - 1];
			if (x - 1 >= 0 && l - 1 >= 0) ans += sum[x - 1][l - 1];
			return ans;
		};
		function<int(int, int, int, int)> f = [&] (int l, int r, int x, int y) {
			int ans = 0;
			if (x - 1 >= 0) {
				for (int j = l; j <= r; j ++) {
					if (a[x - 1][j]) continue;
					int z = min(r, next[x - 1][j]);
					ans = max(ans, f(j, z, x - 1, y) + z - j + 1);
					j = z;
				}
			}
			if (y + 1 < n) {
				for (int j = l; j <= r; j ++) {
					if (a[y + 1][j]) continue;
					int z = min(r, next[y + 1][j]);
					int ll = y + 1, rr = n, mid;
					while (ll < rr) {
						mid = (ll + rr) / 2;
						if (summ(j, z, x, mid) == 0) ll = mid + 1;
						else rr = mid;
					}
					ll --;
					ans = max(ans, f(j, z, x, ll) + (z - j + 1) * (ll - y));
					j = z;
				}
			}
			return ans;
		};
		for (int i = 0; i < n; i ++) {
			for (int j = 0; j < n; j ++) {
				sum[i][j] += a[i][j];
				if (j) sum[i][j] += sum[i][j - 1];
			}
		}
		for (int i = 1; i < n; i ++) {
			for (int j = 0; j < n; j ++) sum[i][j] += sum[i - 1][j];
		}
		for (int i = 0; i < n; i ++) {
			if (a[i][n - 1] == 0) next[i][n - 1] = n - 1;
			else next[i][n - 1] = n - 2;
			for (int j = n - 2; j >= 0; j --) {
				if (a[i][j]) next[i][j] = j - 1;
				else next[i][j] = next[i][j + 1];
			}
		}
		int ans = 0;
		for (int i = 0; i < n; i ++) {
			for (int j = 0; j < n; j ++) {
				if (a[i][j]) continue;
				ans = max(ans, f(j, next[i][j], i, i) + next[i][j] - j + 1);
				j = next[i][j];
			}
		}
		return ans;
	}
	else{
		int empty_cells=0;
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if(F[i][j]==0){
					empty_cells++;
				}	
			}
		}
		bool si=true;
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if(F[i][j]==1){
					continue;
				}
				priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>>cola;
				int dx[]={1,0,-1,0};
				int dy[]={0,1,0,-1};
				vector<vector<int>>dist(N,vector<int>(N,INT_MAX));
				dist[i][j]=0;
				cola.push({0,i,j});
				while(!cola.empty()){
					auto[d,x,y]=cola.top();
					cola.pop();
					for(int dir=0;dir<4;dir++){
						int posi=x+dx[dir];
						int posj=y+dy[dir];
						while(true){
							if(!limites(N,posi,posj)||F[posi][posj]==1)break;
							if((d+1)<dist[posi][posj]){
								dist[posi][posj]=d+1;
								cola.push({dist[posi][posj],posi,posj});
							}
							posi+=dx[dir];
							posj+=dy[dir];
						}
					}
				}
				for(int x=0;x<N;x++){
					for(int y=0;y<N;y++){
						if(F[x][y]==0&&(dist[x][y]>=3||dist[x][y]==-1)){
							si=false;
						}
					}
				}
				if(!si){
					break;
				}
			}
			if(!si){
				break;
			}
		}
		if(si){
			return empty_cells;
		}
		else{
			return 1;
		}
	}
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 12 ms 2204 KB ok
9 Correct 217 ms 39504 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 600 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 600 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 344 KB ok
25 Correct 1 ms 348 KB ok
26 Correct 1 ms 348 KB ok

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 600 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 344 KB ok
27 Correct 1 ms 348 KB ok
28 Correct 1 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Partially correct 1 ms 348 KB partial
31 Partially correct 0 ms 348 KB partial
32 Partially correct 0 ms 348 KB partial
33 Partially correct 0 ms 344 KB partial
34 Correct 3 ms 348 KB ok
35 Correct 13 ms 348 KB ok
36 Partially correct 1 ms 348 KB partial
37 Partially correct 1 ms 348 KB partial
38 Partially correct 0 ms 348 KB partial
39 Partially correct 1 ms 348 KB partial
40 Partially correct 1 ms 348 KB partial
41 Partially correct 0 ms 348 KB partial

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 600 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 344 KB ok
27 Correct 1 ms 348 KB ok
28 Correct 1 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Partially correct 1 ms 348 KB partial
31 Partially correct 0 ms 348 KB partial
32 Partially correct 0 ms 348 KB partial
33 Partially correct 0 ms 344 KB partial
34 Correct 3 ms 348 KB ok
35 Correct 13 ms 348 KB ok
36 Partially correct 1 ms 348 KB partial
37 Partially correct 1 ms 348 KB partial
38 Partially correct 0 ms 348 KB partial
39 Partially correct 1 ms 348 KB partial
40 Partially correct 1 ms 348 KB partial
41 Partially correct 0 ms 348 KB partial
42 Partially correct 71 ms 3908 KB partial
43 Partially correct 53 ms 3420 KB partial
44 Partially correct 293 ms 5024 KB partial
45 Partially correct 455 ms 7876 KB partial
46 Partially correct 109 ms 4308 KB partial
47 Partially correct 791 ms 7376 KB partial
48 Execution timed out 4536 ms 6904 KB Time limit exceeded
49 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 12 ms 2204 KB ok
10 Correct 217 ms 39504 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 600 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 0 ms 344 KB ok
32 Correct 1 ms 348 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 0 ms 348 KB ok
35 Partially correct 1 ms 348 KB partial
36 Partially correct 0 ms 348 KB partial
37 Partially correct 0 ms 348 KB partial
38 Partially correct 0 ms 344 KB partial
39 Correct 3 ms 348 KB ok
40 Correct 13 ms 348 KB ok
41 Partially correct 1 ms 348 KB partial
42 Partially correct 1 ms 348 KB partial
43 Partially correct 0 ms 348 KB partial
44 Partially correct 1 ms 348 KB partial
45 Partially correct 1 ms 348 KB partial
46 Partially correct 0 ms 348 KB partial
47 Partially correct 71 ms 3908 KB partial
48 Partially correct 53 ms 3420 KB partial
49 Partially correct 293 ms 5024 KB partial
50 Partially correct 455 ms 7876 KB partial
51 Partially correct 109 ms 4308 KB partial
52 Partially correct 791 ms 7376 KB partial
53 Execution timed out 4536 ms 6904 KB Time limit exceeded
54 Halted 0 ms 0 KB -