Submission #916632

#	Time	Username	Problem	Language	Result	Execution time	Memory
916632		abcvuitunggio	Soccer Stadium (IOI23_soccer)	C++17	48 / 100	4474 ms	487528 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=32,inf=1e9;
int n,ans,dp[2][mxn][mxn][mxn][mxn][mxn][2];
vector <vector <int>> s;
int sum(int i, int l, int r){
    return s[i][r]-s[i][l-1];
}
int biggest_stadium(int N, vector <vector <int>> F){
    n=N;
    s.resize(N+2);
    for (int i=0;i<N+2;i++){
        s[i].assign(N+2,0);
        if (i&&i<N+1)
            for (int j=1;j<=N;j++)
                s[i][j]=s[i][j-1]+F[i-1][j-1];
    }
    for (int i=1;i<=N;i++){
        int cur=-1;
        for (int j=0;j<N;j++){
            if (F[i-1][j])
                cur=j;
            ans=max(ans,j-cur);
        }
    }
    for (int i=0;i<=N;i++){
        for (int j=N+1;j>i;j--)
            for (int l=N;l;l--)
                for (int r=1;r<=N;r++)
                    for (int u=N;u;u--)
                        for (int v=u;v<=N;v++)
                            for (int b=1;b>=0;b--){
                                if (l>r||u>v||!((l>=u&&r<=v)||(l<=u&&r>=v))){
                                    dp[i&1][j][l][r][u][v][b]=-inf;
                                    continue;
                                }
                                int res=0,x=(r-l+1>v-u+1?i:j);
                                if (!b)
                                    res=dp[i&1][j][l][r][u][v][1];
                                if (b)
                                    x=i^j^x;
                                if (x==i){
                                    if (i){
                                        res=max(res,max(dp[i&1][j][l+1][r][u][v][b],dp[i&1][j][l][r-1][u][v][b]));
                                        if (!sum(i,l,r))
                                            res=max(res,dp[(i&1)^1][j][l][r][u][v][b]+r-l+1);
                                    }
                                }
                                else if (j<=n){
                                    res=max(res,max(dp[i&1][j][l][r][u+1][v][b],dp[i&1][j][l][r][u][v-1][b]));
                                    if (!sum(j,u,v))
                                        res=max(res,dp[i&1][j+1][l][r][u][v][b]+v-u+1);
                                }
                                dp[i&1][j][l][r][u][v][b]=res;
                                if (i<N&&j==i+1&&l==1&&r==N&&u==1&&v==N&&!b)
                                    ans=max(ans,res);
                            }

    }
    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