제출 #915922

#제출 시각아이디문제언어결과실행 시간메모리
915922biank축구 경기장 (IOI23_soccer)C++17
65.50 / 100
1495 ms55572 KiB
#include <bits/stdc++.h> using namespace std; #define ALL(x) x.begin(),x.end() #define SIZE(x) (int)x.size() #define forsn(i,s,n) for(int i=int(s);i<int(n);i++) #define forn(i,n) for(int i=0;i<int(n);i++) #define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--) #define dforn(i,n) for(int i=int(n)-1;i>=0;i--) #define fst first #define snd second typedef pair<int,int> ii; const int MAXN = 500; int f[MAXN][MAXN]; int dp[MAXN][MAXN]; ii ran[MAXN][MAXN]; int L[MAXN][MAXN], R[MAXN][MAXN]; int n; pair<int,ii> solve(int l, int r, int p) { if(l>r) return {0LL,{-1,n}}; if(dp[l][r]!=-1) return {dp[l][r],ran[l][r]}; auto calculate = [&](pair<int,ii> prev, int i) { auto [val,range] = prev; int mini = max(range.fst, L[i][p]), maxi = min(range.snd, R[i][p]); return (pair<int,ii>){val+max(maxi-mini-1,0),{mini,maxi}}; }; pair<int,ii> res = max(calculate(solve(l+1,r,p),l), calculate(solve(l,r-1,p),r)); dp[l][r]=res.fst, ran[l][r]=res.snd; return res; } int only_check(vector<vector<int>> f) { forn(i,n) { int prev=1, count=0; forn(j,n) { if(f[i][j]!=prev) count++; prev=f[i][j]; } if(prev!=1) count++; if(count!=2 && count!=0) return -1; } forn(j,n) { int prev=1, count=0; forn(i,n) { if(f[i][j]!=prev) count++; prev=f[i][j]; } if(prev!=1) count++; if(count!=2 && count!=0) return -1; } vector<int> l(n,0), r(n,n); forn(i,n) forn(j,n) { if(f[i][j]==0) { l[i]=j; break; } } forn(i,n) dforn(j,n) { if(f[i][j]==0) { r[i]=j; break; } } bool flag=false; forn(i,n-1) { if(l[i]<l[i+1]) flag=true; if(l[i]>l[i+1] && flag) return -1; } flag=false; forn(i,n-1) { if(r[i]>r[i+1]) flag=true; if(r[i]<r[i+1] && flag) return -1; } int count=0; forn(i,n) forn(j,n) { count += f[i][j]==0; } return count; } int biggest_stadium(int N, vector<vector<int>> F) { n=N; if(n>500) return only_check(F); forn(i,n) forn(j,n) { f[i][j]=F[i][j]; } forn(i,n) { int k=-1; forn(j,n) { if(f[i][j]==1) k=j; L[i][j]=k; } } forn(i,n) { int k=n; dforn(j,n) { if(f[i][j]==1) k=j; R[i][j]=k; } } int ans=0; forn(i,n) { memset(dp,-1,sizeof dp); ans=max(ans,solve(0,n-1,i).fst); } 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...