Submission #1077299

#TimeUsernameProblemLanguageResultExecution timeMemory
1077299emptypringlescanSoccer Stadium (IOI23_soccer)C++17
0 / 100
4558 ms9812 KiB
#include <bits/stdc++.h> using namespace std; int biggest_stadium(int n,vector<vector<int> > arr){ int close[2][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; } } 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=0; a<n; a++){ for(int b=0; b<n; b++){ for(int c=0; c<=a; c++){ for(int d=0; d<=b; d++){ if(pref[a+1][b+1]-pref[a+1][d]-pref[c][b+1]+pref[c][d]) continue; ans=max(ans,n*n-yay[0][c][b+1]-yay[1][a+1][b+2]-yay[2][c+1][d]-yay[3][a+2][d+1]); } } } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...