Submission #928178

#	Time	Username	Problem	Language	Result	Execution time	Memory
928178		abcvuitunggio	Soccer Stadium (IOI23_soccer)	C++17	48 / 100	29 ms	24244 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=32,inf=1e9;
int n,ans,dp[mxn][mxn][mxn][mxn],s[2001][2001];
int sum(int l, int r, int i){
    return s[r][i]-(l?s[l-1][i]:0);
}
int f(int i, int j, int l, int r){
    if (i==j)
        return 0;
    if (dp[i][j][l][r]!=-1)
        return dp[i][j][l][r];
    dp[i][j][l][r]=max(f(i+1,j,l,r),f(i,j-1,l,r));
    if (l&&!sum(i,j-1,l-1))
        dp[i][j][l][r]=max(dp[i][j][l][r],f(i,j,l-1,r)+j-i);
    if (r<n&&!sum(i,j-1,r))
        dp[i][j][l][r]=max(dp[i][j][l][r],f(i,j,l,r+1)+j-i);
    return dp[i][j][l][r];
}
int biggest_stadium(int N, vector <vector <int>> F){
    n=N;
    for (int i=0;i<N;i++)
        for (int j=0;j<N;j++)
            s[i][j]=(i?s[i-1][j]:0)+F[i][j];
    memset(dp,-1,sizeof(dp));
    for (int i=0;i<=n;i++)
        ans=max(ans,f(0,n,i,i));
    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