Submission #1065105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065105		vjudge1	Soccer Stadium (IOI23_soccer)	C++17	25 / 100	242 ms	55636 KiB

soccer

#include "bits/stdc++.h"
using namespace std;
int pref[2010][2010],dp[31][31][31][31];
inline int allempty(int col,int l,int r){
    return pref[col][r]==pref[col][l-1];
}
int ifall(int N){
    vector<pair<int,int>>rng(N,{0,-1});
    int oth,oth2=oth=N*N;
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) if(allempty(i,j,j))
        rng[i-1].second=j,rng[i-1].first+=!rng[i-1].first*j;
    else oth--,oth2--;
    for(auto[i,j]:rng)
        oth-=j-i+1;
    if(oth) return 0;
    for(auto[i,j]:rng)
        for(auto[i2,j2]:rng)
            if(i&&i2&&i<i2&&j<j2)
                return 0;
    for(auto&[i,j]:rng)
        j-=i-1;
    int dec=0;
    for(int i=1;i<N;i++)
        if(rng[i].second<rng[i-1].second)
            dec=1;
        else if(dec&&rng[i].second>rng[i-1].second)
            return 0;
    return oth2;
}
int biggest_stadium(int N, vector<vector<int>> F) {
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)
        pref[i+1][j+1] = F[i][j]+pref[i+1][j];
    if(N>0) return ifall(N);
    memset(dp,-2,sizeof dp);
    int ans=0;
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++)
        for(int k=j;k<=N;k++) if(allempty(i,j,k))
                ans=max(ans,dp[i][i][j][k]=k-j+1);
    for(int sz=1;sz<N;sz++) {
        for(int c2=sz+1;c2<=N;c2++){
            int c1=c2-sz;
            for(int l1=1;l1<=N;l1++){
                for(int r1=l1;r1<=N;r1++){
                    if(!allempty(c1,l1,r1))goto h1;
                    for(int l2=l1;l2;l2--) for(int r2=r1;r2<=N;r2++)
                        dp[c1][c2][l1][r1]=max(dp[c1][c2][l1][r1],dp[c1+1][c2][l2][r2]);
                    h1:
                    if(!allempty(c2,l1,r1))goto h2;
                    for(int l2=l1;l2;l2--) for(int r2=r1;r2<=N;r2++)
                        dp[c1][c2][l1][r1]=max(dp[c1][c2][l1][r1],dp[c1][c2-1][l2][r2]);
                    h2:
                    ans=max(ans,dp[c1][c2][l1][r1]+=r1-l1+1);
                }
            }
        }
    }
    return ans;
}

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