Submission #1065076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065076		vjudge1	Soccer Stadium (IOI23_soccer)	C++17	48 / 100	19 ms	7884 KiB

soccer

#include "bits/stdc++.h"
using namespace std;
int pref[31][31],dp[31][31][31][31];
inline int allempty(int col,int l,int r){
    return pref[col][r]==pref[col][l-1];
}
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];
    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: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30