Submission #939403

#	Time	Username	Problem	Language	Result	Execution time	Memory
939403		Wansur	Soccer Stadium (IOI23_soccer)	C++17	65.50 / 100	2360 ms	523244 KiB

soccer

#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'

typedef long long ll;
using namespace std;
struct seg{
    int m1,m2,sum,cnt;
};

const string out[2]={"NO\n","YES\n"};

const ll dx[]={0,1,0,-1,-1,1,1,-1};
const ll dy[]={1,0,-1,0,-1,1,-1,1};
const int mod=998244353;
const int md=1e9+7;
const int mx=2e3+12;
const bool T=0;

int dp[512][512][512];
int pref[mx][mx];
int a[mx][mx];
int n;

int get(int i,int l,int r){
    if(!l)return pref[i][r];
    return pref[i][r]-pref[i][l-1];
}

int biggest_stadium(int N, vector<vector<int>> B) {
    n = N;
    if (n > 500) {
        return 0;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            a[i][j]=B[i][j];
            pref[i][j]=a[i][j];
            if(j) pref[i][j]+=pref[i][j-1];
        }
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                dp[i][j][k]=-1e9;
            }
        }
    }
    int ans=0;

    for(int len=n;len>=1;len--){
        for(int l=0;l+len-1<n;l++){
            int r=l+len-1;
            for(int i=0;i<n;i++){
                if(get(i,l,r)) {
                    continue;
                }
                int j=i;
                while(j<n-1 && !get(j+1,l,r)){
                    j++;
                }
                dp[i][l][r]=(j-i+1)*(r-l+1);
                if(l>0){
                    for(int s=i;s<=j;s++){
                        if(get(s,l-1,r)){
                            continue;
                        }
                        int t=s;
                        while(t<n-1 && !get(t+1,l-1,r)){
                            t++;
                        }
                        dp[i][l][r]=max(dp[i][l][r], dp[s][l-1][r] + ((j-i+1) - (t-s+1)) * (r-l+1));
                        s=t;
                    }
                }
                if(r<n-1){
                    for(int s=i;s<=j;s++){
                        if(get(s,l,r+1)){
                            continue;
                        }
                        int t=s;
                        while(t<n-1 && !get(t+1,l,r+1)){
                            t++;
                        }
                        dp[i][l][r]=max(dp[i][l][r], dp[s][l][r+1] + ((j-i+1) - (t-s+1)) * (r-l+1));
                        s=t;
                    }
                }
                ans=max(ans,dp[i][l][r]);
                i=j;
            }
        }

    }
    return ans;
}

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