# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1059706 | 2024-08-15T07:22:56 Z | epicci23 | Soccer Stadium (IOI23_soccer) | C++17 | 0 ms | 0 KB |
#include "bits/stdc++.h" #define int long long #define all(v) v.begin() , v.end() #define sz(a) (int)a.size() using namespace std; #include "soccer.h" int dp[8][8][8][8][8][8]; vector<vector<int>> ar; int ans=0,n; int f(int a,int b,int c,int d,int e,int f){ if(dp[a][b][c][d][e][f]!=-1) return dp[a][b][c][d][e][f]; int cevv=0; for(int i=b;i<=c;i++) if(ar[a][i]) return dp[a][b][c][d][e][f]=0; for(int i=e;i<=f;i++) if(ar[d][i]) return dp[a][b][c][d][e][f]=0; if(a>0){ for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ if(ar[a-1][j]) break; if(b<=i && j<=c && ((i<=e && f<=j) || (e<=i && j<=f)) ) cevv=max(cevv,f(a-1,i,j,d,e,f)+j-i+1); } } } if(d+1<n){ for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ if(ar[d+1][j]) break; if(e<=i && j<=f && ((i<=b && c<=j) || (b<=i && j<=c)) ) cevv=max(cevv,f(a,b,c,d+1,i,j)+j-i+1); } } } return dp[a][b][c][d][e][f]=cevv; } int biggest_stadium(int N, vector<vector<int>> xd){ memset(dp,-1,sizeof(dp)); ar=xd;n=N; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ for(int k=j;k<n;k++){ if(ar[i][k]) break; ans=max(ans,f(i,j,k,i,j,k)+k-j+1); } } } return ans; } /*void _(){ } int32_t main(){ cin.tie(0); ios::sync_with_stdio(0); int tc=1;//cin >> tc; while(tc--) _(); return 0; }*/