Submission #916360

#TimeUsernameProblemLanguageResultExecution timeMemory
916360chirathnirodhaSoccer Stadium (IOI23_soccer)C++17
8 / 100
254 ms38888 KiB
#include "soccer.h" #include<bits/stdc++.h> using namespace std; #define PB push_back #define MP make_pair #define F first #define S second #define P push #define I insert typedef long long ll; int n,ans; bool valid(vector<int> v){ bool arr[n][n]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(v[i*n+j])arr[i][j]=1; else arr[i][j]=0; } } int pos[n][n][4]; for(int i=0;i<n;i++){ int cur=-1; //left for(int j=0;j<n;j++){ pos[i][j][0]=cur; if(arr[i][j])cur=j; } cur=n; //right for(int j=n-1;j>=0;j--){ pos[i][j][1]=cur; if(arr[i][j])cur=j; } cur=0; //up for(int j=0;j<n;j++){ pos[j][i][2]=cur; if(arr[j][i])cur=j; } cur=n; //down for(int j=n-1;j>=0;j--){ pos[j][i][3]=cur; if(arr[j][i])cur=j; } } for(int a=0;a<n;a++){ for(int b=0;b<n;b++){ if(arr[a][b]==1)continue; for(int c=a;c<n;c++){ for(int d=b;d<n;d++){ bool ok1=false,ok2=false; if(pos[a][b][1]>d && pos[c][d][2]<a)ok1=true; if(pos[a][b][3]>c && pos[c][d][0]<b)ok2=true; if(!ok1 && !ok2)return false; } } } } return true; } void comput(vector<int> v,int cur,int siz){ if(cur==n*n)if(valid(v)){ans=max(ans,siz);return;} for(int i=cur;i<n*n;i++){ if(v[i]==-1){ v[i]=0; comput(v,i+1,siz+1); v[i]=1; comput(v,i+1,siz); v[i]=-1; } } return; } int biggest_stadium(int N, vector<vector<int>> F){ n=N; ans=0; int trees=0;pair<int,int> tr; for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(F[i][j]){trees++;tr={i,j};} if(trees==0)return n*n; if(trees==1){ int x=tr.F,y=tr.S; int a=n*x+y*(n-x) , b=n*x+(n-x)*(n-y-1) , c=n*(n-x-1)+y*(x+1) , d=n*(n-x-1)+(x+1)*(n-y-1); return max(max(a,b),max(c,d)); } vector<int> v; v.assign(n*n,-1); if(n<=3){ for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(F[i][j])v[i*n+j]=1; comput(v,0,0); return ans; } for(int i=0;i<n;i++)for(int j=0;j<n;j++){ if(F[i][j])v[i*n+j]=1; else v[i*n+j]=0; } if(valid(v))return n*n-trees; else return 0; }
#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...