Submission #885890

#	Time	Username	Problem	Language	Result	Execution time	Memory
885890		jay_jayjay	Soccer Stadium (IOI23_soccer)	C++17	64 / 100	4558 ms	118100 KiB

soccer

// {{{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;
        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++)
                        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];
        }
        //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));
        //}
//}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 16 / 16
• Subtask 6: 0 / 30