Submission #1068152

#TimeUsernameProblemLanguageResultExecution timeMemory
1068152AdamGSSoccer Stadium (IOI23_soccer)C++17
64 / 100
4562 ms991720 KiB
#include "soccer.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=2e3+7; map<pair<pair<int,int>,pair<int,int>>,int>mp; vector<int>P[LIM], pole; vector<pair<int,int>>V[LIM*LIM*2]; int lewo[LIM], prawo[LIM], odw[LIM], lst[LIM], dp[LIM*LIM*2], czy[LIM*LIM*2], ile[LIM], akt, ans; void DFS(int x) { czy[x]=1; for(auto i : V[x]) { if(!czy[i.st]) DFS(i.st); dp[x]=max(dp[x], dp[i.st]+i.nd); } ans=max(ans, dp[x]+pole[x]); } int biggest_stadium(int n, vector<vector<int>>T) { pole.pb(0); rep(i, n) { rep(j, n) { ++ile[j]; if(T[i][j]) ile[j]=0; } rep(j, n+1) { P[j].clear(); lewo[j]=prawo[j]=j; odw[j]=0; lst[j]=n; } rep(j, n) P[ile[j]].pb(j); for(int j=n; j; --j) for(auto l : P[j]) { vector<pair<pair<int,int>,pair<int,int>>>A; int a=l, b=l; if(l && odw[l-1]) { A.pb({{lewo[l-1], l-1}, {i, i-lst[l-1]+1}}); a=lewo[l-1]; } if(l+1<n && odw[l+1]) { A.pb({{l+1, prawo[l+1]}, {i, i-lst[l+1]+1}}); b=prawo[l+1]; } pair<pair<int,int>,pair<int,int>>x={{a, b}, {i, i-j+1}}; if(!mp[x]) { mp[x]=++akt; pole.pb((x.st.nd-x.st.st+1)*(x.nd.st-x.nd.nd+1)); } int k=mp[x]; for(auto c : A) V[k].pb({mp[c], (c.st.nd-c.st.st+1)*(x.nd.nd-c.nd.nd)}); if(j>1) V[mp[{{a, b}, {i-1, i-j+1}}]].pb({k, b-a+1}); odw[l]=1; lewo[b]=a; prawo[a]=b; lst[a]=lst[b]=j; } } rep(i, n) ile[i]=0; for(int i=n-1; i>=0; --i) { rep(j, n) { ++ile[j]; if(T[i][j]) ile[j]=0; } rep(j, n+1) { P[j].clear(); lewo[j]=prawo[j]=j; odw[j]=0; lst[j]=n; } rep(j, n) P[ile[j]].pb(j); for(int j=n; j; --j) for(auto l : P[j]) { vector<pair<pair<int,int>,pair<int,int>>>A; int a=l, b=l; if(l && odw[l-1]) { A.pb({{lewo[l-1], l-1}, {i+lst[l-1]-1, i}}); a=lewo[l-1]; } if(l+1<n && odw[l+1]) { A.pb({{l+1, prawo[l+1]}, {i+lst[l+1]-1, i}}); b=prawo[l+1]; } pair<pair<int,int>,pair<int,int>>x={{a, b}, {i+j-1, i}}; if(!mp[x]) { mp[x]=++akt; pole.pb((x.st.nd-x.st.st+1)*(x.nd.st-x.nd.nd+1)); } int k=mp[x]; for(auto c : A) { V[k].pb({mp[c], (c.st.nd-c.st.st+1)*(c.nd.st-x.nd.st)}); } odw[l]=1; lewo[b]=a; prawo[a]=b; lst[a]=lst[b]=j; } } rep(i, akt) if(!czy[i+1]) DFS(i+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...