Submission #1240730

#TimeUsernameProblemLanguageResultExecution timeMemory
1240730noyancanturkSoccer Stadium (IOI23_soccer)C++17
70 / 100
4599 ms153584 KiB
#include "soccer.h" #pragma GCC optimize("O3,unroll-loops") #include<bits/stdc++.h> using namespace std; #define pb push_back using pii=pair<int,int>; const int lim=2100; int n; struct{ pii tree[2*lim+1]; pii query(int l,int r){ // assert(l<=r); // cerr<<l<<' '<<r<<'\n'; int ansmin=INT_MIN; int ansmax=INT_MAX; for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){ if(l&1){ ansmin=max(ansmin,tree[l].first); ansmax=min(ansmax,tree[l].second); l++; } if(r&1){ r--; ansmin=max(ansmin,tree[r].first); ansmax=min(ansmax,tree[r].second); } } return {ansmin,ansmax}; } void update(int p,pii val){ tree[p+=n]=val; for(p>>=1;p;p>>=1){ tree[p].first=max(tree[p<<1].first,tree[p<<1|1].first); tree[p].second=min(tree[p<<1].second,tree[p<<1|1].second); } } }st[lim]; int dp[lim][lim]; vector<pii>have[lim]; int biggest_stadium(int N,vector<vector<int>>a){ n=N; int haveup[n][n],havedown[n][n]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ haveup[i][j]=-1; havedown[i][j]=n; } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(a[i][j]){ haveup[i][j]=i; }else if(i){ haveup[i][j]=haveup[i-1][j]; } } } for(int i=n-1;0<=i;i--){ for(int j=0;j<n;j++){ if(a[i][j]){ havedown[i][j]=i; }else if(i!=n-1){ havedown[i][j]=havedown[i+1][j]; } } } // for(int i=0;i<n;i++){ // for(int j=0;j<n;j++){ // cerr<<haveup[i][j]<<' '; // }cerr<<'\n'; // }cerr<<'\n'; // for(int i=0;i<n;i++){ // for(int j=0;j<n;j++){ // cerr<<havedown[i][j]<<' '; // }cerr<<'\n'; // }cerr<<'\n'; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ st[i].update(j,pii{haveup[i][j],havedown[i][j]}); } } vector<int>inds[n]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(a[i][j]){ inds[i].pb(j); } } } int ans=0; for(int i=0;i<n;i++){ for(int j=0;j<=n;j++){ for(auto[x,y]:have[j]){ dp[x][y]=0; } have[j].clear(); } // cerr<<"at mid "<<i<<'\n'; auto insert=[&](pii x,int val) -> void { if(!dp[x.first][x.second])have[x.second-x.first].pb(x); dp[x.first][x.second]=max(dp[x.first][x.second],val); // cerr<<"left\n"; }; auto trans=[&](pii x,int plim,int past) -> void { if(x.second<x.first)return; pii lims=st[i].query(x.first,x.second); // cerr<<x.first<<' '<<x.second<<" can go till "<<lims.first<<' '<<lims.second<<'\n'; insert(x,past+(x.second-x.first+1)* (lims.second-lims.first-1-plim)); }; int last=-1; for(int j=0;j<n;j++){ if(a[i][j]){ trans({last+1,j-1},0,0); last=j; } } trans({last+1,n-1},0,0); for(int sz=n;0<=sz;sz--){ for(auto[x,y]:have[sz]){ // cerr<<x<<' '<<y<<" :: "<<val<<'\n'; int val=dp[x][y]; ans=max(ans,val); pii stuck=st[i].query(x,y); int did=stuck.second-stuck.first-1; for(int j:{stuck.first,stuck.second}){ // cerr<<j<<'\n'; if(j<0||n<=j)continue; last=x-1; auto p=upper_bound(inds[j].begin(),inds[j].end(),last); while(p!=inds[j].end()&&*p<=y){ // cerr<<"add "<<last+1<<' '<<(*p)-1<<" because "<<j<<'\n'; trans({last+1,(*p)-1},did,val); last=*p; p++; } trans({last+1,y},did,val); } } } } 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...