Submission #885892

#TimeUsernameProblemLanguageResultExecution timeMemory
885892jay_jayjaySoccer Stadium (IOI23_soccer)C++17
70 / 100
4528 ms118332 KiB
// {{{1 extern "C" int __lsan_is_turned_off() { return 1; } #include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #include <algorithm> #include <complex> #include <iostream> #include <numeric> #include <array> #include <vector> #include <string> #include <deque> #include <queue> #include <map> #include <set> using namespace std; #define ll long long #define inf 0x3f3f3f3f #define infl 0x3f3f3f3f3f3f3f3fll #include <assert.h> #ifdef DEBUG #define dprintf(args...) fprintf(stderr,args) #endif #ifndef DEBUG #define dprintf(args...) 69 #endif #define all(x) (x).begin(), (x).end() // 1}}} #define N 2000 #define LG 20 int n; int F[N][N]; int C[N][N]; int D[N][N]; int dp[N][N],aux[N][N]; int st_l[LG][N]; int st_r[LG][N]; // in col, row void build(int st[LG][N], int m) { for(int lg = 1; lg < LG; lg++) for(int i=0;i+(1<<lg)<=N;i++) // st[lg][i] repr [i...i+(1<<lg)) if(m)st[lg][i] = max(st[lg-1][i],st[lg-1][i+(1<<(lg-1))]); else st[lg][i] = min(st[lg-1][i],st[lg-1][i+(1<<(lg-1))]); } int query(int st[LG][N],int m, int l, int r) { r++; int lg = __lg(r-l); //printf("l=%d r=%d lg=%d 1<<lg=%d\n",l,r,lg,1<<lg); if(m) return max(st[lg][l],st[lg][r-(1<<lg)]); else return min(st[lg][l],st[lg][r-(1<<lg)]); } int solve(int c) { // solves if column of highest is c for(int y=0;y<n;y++) { st_l[0][y] = lower_bound(C[y],C[y]+n,C[y][c])-C[y]; if(C[y][st_l[0][y]]==0)st_l[0][y]--; st_r[0][y] = upper_bound(C[y],C[y]+n,C[y][c])-C[y]; //printf("%d, %d ( : %d)\n",st_l[0][y],st_r[0][y],C[y][c]); } build(st_l,1); build(st_r,0); #define extent(l, r) (query(st_r,0,l,r) - query(st_l,1,l,r) - 1) #define ok(l,r) (query(st_r,0,l,r)>c && query(st_l,1,l,r)<c) #define val(l,r) (ok(l,r)?extent(l,r) : 0) for(int i=0;i<n;i++) { for(int j=n-1;j>=i;j--) { dp[i][j]=val(i,j); } } for(int i=0;i<n;i++) { for(int j=n-1;j>i;j--) { // transition to i+1,j // and i,j-1 // i+1, j aux[i+1][j] = val(i+1,j); dp[i+1][j] = max(dp[i+1][j], (j-i) * (aux[i+1][j]-aux[i][j]) + dp[i][j]); aux[i][j-1] = val(i,j-1); dp[i][j-1] = max(dp[i][j-1], (j-i) * (aux[i][j-1]-aux[i][j]) + dp[i][j]); } } //printf("\nc=%d\n",c); int mx=0; for(int i=0;i<n;i++) for(int j=n-1;j>=i;j--) { mx = max(mx,dp[i][j]); //printf("[%d, %d] = %d\n",i,j,dp[i][j]); } //printf("c=%d: mx=%d\n",c,mx); return mx; } int biggest_stadium(int _n, vector<vector<int>> _f) { n=_n; int tot = 0; for(int i=0;i<n;i++) for(int j=0;j<n;j++) F[i][j]=_f[i][j]; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) tot += F[i][j]; for(int j=0;j<n;j++) C[i][j]=F[i][j]; for(int j=1;j<n;j++) C[i][j]+=C[i][j-1]; } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) D[j][i]=F[j][i]; for(int j=1;j<n;j++) D[j][i]+=D[j-1][i]; } if(tot == 1) { for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(F[i][j]) { int mn = min({ (i+1)*(n-j), (i+1)*(j+1), (n-i)*(j+1), (n-i)*(n-j) }); return n*n-mn; } } //for(int i=0;i<n;i++) { //for(int j=0;j<n;j++) //printf("%d ",F[i][j]); //printf("\n"); //} //printf("\n"); //for(int i=0;i<n;i++) { //for(int j=0;j<n;j++) //printf("%d ",C[i][j]); //printf("\n"); //} int best=0; for(int i=0;i<n;i++)best=max(best,solve(i)); return best; } //int main() //{ //int tt; //scanf("%d",&tt); //for(int ttn=0;ttn<tt;ttn++) //{ //int n; //scanf("%d",&n); //vector f(n,vector<int>(n)); //for(int i=0;i<n;i++) { //for(int j=0;j<n;j++) { //scanf(" %c",&f[i][j]);f[i][j]=f[i][j]=='1'; //} //} //printf("%d\n",biggest_stadium(n,f)); //} //}
#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...