oj.uz

Submission #1077333

# Submission time Handle Problem Language Result Execution time Memory
1077333 2024-08-27T05:30:17 Z emptypringlescan Soccer Stadium (IOI23_soccer) C++17
6 / 100
 496 ms 180560 KB 
#include <bits/stdc++.h>
using namespace std;
int biggest_stadium(int n,vector<vector<int> > arr){
	int close[4][n][n];
	for(int j=0; j<n; j++){
		int prv=-1;
		for(int i=0; i<n; i++){
			if(arr[i][j]) prv=i;
			close[0][i][j]=prv;
		}
		prv=n;
		for(int i=n-1; i>=0; i--){
			if(arr[i][j]) prv=i;
			close[1][i][j]=prv;
		}
	}
	for(int i=0; i<n; i++){
		int prv=-1;
		for(int j=0; j<n; j++){
			if(arr[i][j]) prv=j;
			close[2][i][j]=prv;
		}
		prv=n;
		for(int j=n-1; j>=0; j--){
			if(arr[i][j]) prv=j;
			close[3][i][j]=prv;
		}
	}
	int yay[4][n+5][n+5];
	memset(yay,0,sizeof(yay));
	for(int i=0; i<n; i++){
		vector<pair<int,pair<int,int> > > mono;
		//area 0
		mono.push_back({n+5,{-1,0}});
		int val=0;
		for(int j=0; j<n; j++){
			while(!mono.empty()&&mono.back().first<close[0][i][j]){
				val-=mono.back().second.second;
				mono.pop_back();
			}
			int more=(close[0][i][j]+1)*(j-mono.back().second.first);
			val+=more;
			mono.push_back({close[0][i][j],{j,more}});
			yay[0][i+1][j+1]=val;
		}
		//area 1
		mono.clear();
		mono.push_back({n+5,{n,0}});
		val=0;
		for(int j=n-1; j>=0; j--){
			while(!mono.empty()&&mono.back().first<close[0][i][j]){
				val-=mono.back().second.second;
				mono.pop_back();
			}
			int more=(close[0][i][j]+1)*(mono.back().second.first-j);
			val+=more;
			mono.push_back({close[0][i][j],{j,more}});
			yay[1][i+1][j+1]=val;
		}
		//area 2
		mono.clear();
		mono.push_back({-1,{-1,0}});
		val=0;
		for(int j=0; j<n; j++){
			while(!mono.empty()&&mono.back().first>close[1][i][j]){
				val-=mono.back().second.second;
				mono.pop_back();
			}
			int more=(n-close[1][i][j])*(j-mono.back().second.first);
			val+=more;
			mono.push_back({close[1][i][j],{j,more}});
			yay[2][i+1][j+1]=val;
		}
		//area 3
		mono.clear();
		mono.push_back({-1,{n,0}});
		val=0;
		for(int j=n-1; j>=0; j--){
			while(!mono.empty()&&mono.back().first>close[1][i][j]){
				val-=mono.back().second.second;
				mono.pop_back();
			}
			int more=(n-close[1][i][j])*(mono.back().second.first-j);
			val+=more;
			mono.push_back({close[1][i][j],{j,more}});
			yay[3][i+1][j+1]=val;
		}
	}
	int pref[n+1][n+1];
	memset(pref,0,sizeof(pref));
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			pref[i+1][j+1]=pref[i+1][j]+pref[i][j+1]-pref[i][j]+arr[i][j];
		}
	}
	int ans=0;
	for(int a=1; a<=n; a++){
		for(int b=1; b<=n; b++){
			int v=n*n-yay[0][a][b]-yay[1][a][b]-yay[2][a][b]-yay[3][a][b];
			v+=close[0][a-1][b-1]+1+(n-close[1][a-1][b-1])+close[2][a-1][b-1]+1+(n-close[3][a-1][b-1]);
			//cout << a << ' ' << b << ' ' << yay[0][a][b] << ' ' << yay[1][a][b] << ' ' << yay[2][a][b] << ' ' << yay[3][a][b] << '\n';
			//cout << close[0][a-1][b-1]+1 << ' ' << (n-close[1][a-1][b-1]) << ' ' << close[2][a-1][b-1]+1 << ' ' << (n-close[3][a-1][b-1]) << '\n';
			//cout << v << '\n';
			ans=max(ans,v);
		}
	}
	return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 604 KB ok
7 Correct 2 ms 860 KB ok
8 Correct 31 ms 11612 KB ok
9 Correct 496 ms 180560 KB ok

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 1 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Incorrect 1 ms 348 KB wrong
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 344 KB ok
8 Incorrect 1 ms 348 KB wrong
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 1 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 344 KB ok
10 Incorrect 1 ms 348 KB wrong
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 1 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 344 KB ok
10 Incorrect 1 ms 348 KB wrong
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 344 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 604 KB ok
8 Correct 2 ms 860 KB ok
9 Correct 31 ms 11612 KB ok
10 Correct 496 ms 180560 KB ok
11 Correct 1 ms 344 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 344 KB ok
15 Incorrect 1 ms 348 KB wrong
16 Halted 0 ms 0 KB -