제출 #1087326

#제출 시각아이디문제언어결과실행 시간메모리
1087326urd05축구 경기장 (IOI23_soccer)C++17
70 / 100
4575 ms390724 KiB
#include "soccer.h" #include <bits/stdc++.h> using namespace std; int n; int arr[2001][2001]; typedef pair<int,int> P; typedef pair<P,P> PP; map<long long,int> mp; int psum[2001][2001]; int ri[2001][2001]; int ntr[2001][2001]; const long long three=1e12; const long long two=1e8; const long long one=1e4; int query(int u,int d,int l,int r) { return psum[d][r]-psum[u-1][r]-psum[d][l-1]+psum[u-1][l-1]; } long long hhash(PP x) { return x.first.first*three+x.first.second*two+x.second.first*one+x.second.second; } PP unhash(long long x) { PP ret; ret.second.second=x%(n+1); x/=n+1; ret.second.first=x%(n+1); x/=n+1; ret.first.second=x%(n+1); x/=n+1; ret.first.first=x%(n+1); return ret; } int ans(int l,int r,int u,int d) { long long nw=hhash(PP(P(l,r),P(u,d))); if (mp.find(nw)!=mp.end()) { return mp[nw]; } int now=l; int ret=(d-u+1)*(r-l+1); if (u>1) { while (now<=r) { if (arr[u-1][now]==1) now=ntr[u-1][now]; if (now>r) { break; } int ll=now; int rr=min(ri[u-1][now],r); int uu=u; int dd=d; if (ll<=rr) { int lo=0; int hi=u; int val=psum[u-1][rr]-psum[u-1][ll-1]; while (lo+1<hi) { int mid=(lo+hi)/2; if (-psum[mid-1][rr]+psum[mid-1][ll-1]==-val) { hi=mid; } else { lo=mid; } } uu=hi; ret=max(ret,ans(ll,rr,uu,dd)+(r-l-rr+ll)*(d-u+1)); } now=ri[u-1][now]+1; } } now=l; if (d<n) { while (now<=r) { if (arr[d+1][now]==1) now=ntr[d+1][now]; if (now>r) { break; } int ll=now; int rr=min(ri[d+1][now],r); int uu=u; int dd=d; if (ll<=rr) { int lo=d; int hi=n+1; int val=-psum[d][rr]+psum[d][ll-1]; while (lo+1<hi) { int mid=(lo+hi)/2; if (psum[mid][rr]-psum[mid][ll-1]==-val) { lo=mid; } else { hi=mid; } } dd=lo; ret=max(ret,ans(ll,rr,uu,dd)+(r-l-rr+ll)*(d-u+1)); } now=ri[d+1][now]+1; } } return mp[nw]=ret; } int biggest_stadium(int N, std::vector<std::vector<int>> F) { n=N; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { arr[i+1][j+1]=F[i][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { psum[i][j]=psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1]+arr[i][j]; } } for(int i=1;i<=n;i++) { int pr=0; for(int j=1;j<=n;j++) { if (arr[i][j]==1) { for(int k=pr+1;k<j;k++) { ri[i][k]=j-1; } pr=j; } } for(int j=pr+1;j<=n;j++) { ri[i][j]=n; } pr=1; for(int j=1;j<=n;j++) { if (arr[i][j]==0) { for(int k=pr;k<j;k++) { ntr[i][k]=j; } pr=j; } } for(int k=pr;k<=n;k++) { ntr[i][k]=n+1; } } int ret=0; for(int i=1;i<=n;i++) { int pr=0; for(int j=1;j<=n;j++) { if (arr[i][j]==1) { if (pr+1<=j-1) { ret=max(ret,ans(pr+1,j-1,i,i)); } pr=j; } } if (pr!=n) { ret=max(ret,ans(pr+1,n,i,i)); } } return ret; }
#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...