Submission #842420

#	Time	Username	Problem	Language	Result	Execution time	Memory
842420		firewater	Soccer Stadium (IOI23_soccer)	C++17	64 / 100	4545 ms	146724 KiB

soccer

#include "soccer.h"
#include<bits/stdc++.h>
#define fs first
#define sn second
#define mp make_pair
#define MX 2023
using namespace std;
int n,now,ans,sl,sr,a[MX][MX],sum[MX][MX],stl[MX][20],str[MX][20],fl[MX][MX],fr[MX][MX];
pair<int,pair<int,int> >f[MX][MX];
int get(int A[MX][20],int l,int r)
{
    int k=__lg(r-l+1);
    return min(A[l][k],A[r-(1<<k)+1][k]);
}
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][j-1]+a[i][j];
        }
    for(int i=1;i<=n;++i){
        now=1;
        for(int j=1;j<=n;++j){
            if(a[i][j])now=j+1;
            else fl[i][j]=j-now+1;
        }
        now=n;
        for(int j=n;j>0;--j){
            if(a[i][j])now=j-1;
            else fr[i][j]=now-j+1;
        }
    }
    for(int j=1;j<=n;++j){
        for(int i=1;i<=n;++i){
            stl[i][0]=fl[i][j];
            str[i][0]=fr[i][j];
        }
        for(int k=1;k<=17;++k){
            for(int i=1;i<=n;++i){
                stl[i][k]=min(stl[i][k-1],(i+(1<<k-1)<=n?stl[i+(1<<k-1)][k-1]:n));
                str[i][k]=min(str[i][k-1],(i+(1<<k-1)<=n?str[i+(1<<k-1)][k-1]:n));
            }
        }
        for(int i=1;i<=n;++i)
            for(int k=i;k<=n;++k)
                f[i][k]=mp(0,mp(0,0));
        for(int i=1;i<=n;++i)
            f[i][i]=mp(max(0,fl[i][j]+fr[i][j]-1),mp(fl[i][j],fr[i][j]));
        for(int len=1;len<=n;++len)
            for(int i=1;i<=n-len+1;++i){
                int k=i+len-1;
                ans=max(ans,f[i][k].fs);
                if(i>1){
                    sl=min(f[i][k].sn.fs,fl[i-1][j]);
                    sr=min(f[i][k].sn.sn,fr[i-1][j]);
                    f[i-1][k]=max(f[i-1][k],mp(f[i][k].fs+max(sl+sr-1,0),mp(sl,sr)));
                }
                if(k<n){
                    sl=min(f[i][k].sn.fs,fl[k+1][j]);
                    sr=min(f[i][k].sn.sn,fr[k+1][j]);
                    f[i][k+1]=max(f[i][k+1],mp(f[i][k].fs+max(sl+sr-1,0),mp(sl,sr)));
                }
            }
    }
    return ans;
}

Compilation message (stderr)

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:43:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   43 |                 stl[i][k]=min(stl[i][k-1],(i+(1<<k-1)<=n?stl[i+(1<<k-1)][k-1]:n));
      |                                                  ~^~
soccer.cpp:43:69: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   43 |                 stl[i][k]=min(stl[i][k-1],(i+(1<<k-1)<=n?stl[i+(1<<k-1)][k-1]:n));
      |                                                                    ~^~
soccer.cpp:44:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   44 |                 str[i][k]=min(str[i][k-1],(i+(1<<k-1)<=n?str[i+(1<<k-1)][k-1]:n));
      |                                                  ~^~
soccer.cpp:44:69: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   44 |                 str[i][k]=min(str[i][k-1],(i+(1<<k-1)<=n?str[i+(1<<k-1)][k-1]:n));
      |                                                                    ~^~

• 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