Submission #846983

#	Time	Username	Problem	Language	Result	Execution time	Memory
846983		firewater	Soccer Stadium (IOI23_soccer)	C++17	54 / 100	4541 ms	112936 KiB

soccer

#include "soccer.h"
#include<bits/stdc++.h>
#define fs first
#define sn second
#define MX 2020
using namespace std;
int n,ans,a[MX][MX],sum[MX][MX];
map<pair<int,pair<int,int> >,int>f;
pair<int,int>sav;
int get(int x1,int x2,int y1,int y2)
{
    if(x1>x2||y1>y2)return 0;
    return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
pair<int,int>find(int x,int L,int R)
{
    int ansl,ansr,l,r;
    l=1;r=x+1;
    while(l<r){
        int mid=l+r>>1;
        if(!get(mid,x,L,R))r=mid;
        else l=mid+1;
    }
    ansl=l;
    l=x-1;r=n;
    while(l<r){
        int mid=l+r+1>>1;
        if(!get(x,mid,L,R))l=mid;
        else r=mid-1;
    }
    ansr=l;
    return {ansl,ansr};
}
int solve(int x,int L,int R)
{
    if(f.count({x,{L,R}}))return f[{x,{L,R}}];

    pair<int,int>sav=find(x,L,R),k;
    int num=(R-L+1)*max(0,sav.sn-sav.fs+1),l,r;

    if(sav.fs==1&&sav.sn==n)return f[{x,{L,R}}]=num;
    if(x>sav.fs)return f[{x,{L,R}}]=solve(sav.fs,L,R);

    for(int li=L,ri=L;li<=R;++li,ri=max(li,ri)){
        if((sav.fs==1||get(sav.fs-1,x,li,ri))&&(sav.sn==n||get(x,sav.sn+1,li,ri)))continue;
        l=ri;
        r=R;
        while(l<r){
            int mid=l+r+1>>1;
            if((sav.fs>1&&!get(sav.fs-1,x,li,mid))||(sav.sn<n&&!get(x,sav.sn+1,li,mid)))l=mid;
            else r=mid-1;
        }
        ri=l;
        k=find(x,li,ri);
        num=max(num,solve(x,li,ri)+(R-ri+li-L)*max(0,sav.sn-sav.fs+1));
        ri++;
    }
    return f[{x,{L,R}}]=num;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    n=N;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j){
            a[i][j]=F[i-1][j-1];
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
        }
    for(int i=1;i<=n;++i){
        sav=find(i,1,n);
        ans=max(ans,solve(i,1,n));
    }
    return ans;
}

Compilation message (stderr)

soccer.cpp: In function 'std::pair<int, int> find(int, int, int)':
soccer.cpp:20:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |         int mid=l+r>>1;
      |                 ~^~
soccer.cpp:27:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         int mid=l+r+1>>1;
      |                 ~~~^~
soccer.cpp: In function 'int solve(int, int, int)':
soccer.cpp:49:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |             int mid=l+r+1>>1;
      |                     ~~~^~

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