Submission #1343419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1343419		allin27x	Soccer Stadium (IOI23_soccer)	C++17	48 / 100	4593 ms	3936 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
#define _max(x,y) x = max(x,y)
using namespace std;


const int N = 31;
int dp[N][N][N][N];
const int INF = 1e9;

int biggest_stadium(int n, std::vector<std::vector<int>> A)
{
    for (int u=0; u<n; u++){
        for (int d=n-1; d>=u; d--){
            for (int l=0; l<n; l++){
                for (int r=l; r<n; r++){
                    dp[u][d][l][r] = -INF;
                    int s = 0; for (int j=l; j<=r; j++) s += !A[u][j] + !A[d][j];
                    if (s != 2 * (r-l+1)) continue;
                    dp[u][d][l][r] = 2*(r-l+1);
                    if (u>0){
                        for (int x=l; x<=r;){
                            if (A[u-1][x]) {x++; continue;}
                            int y = x; while (y<=r&&!A[u-1][y]) y++; y--;
                            _max(dp[u][d][l][r], dp[u-1][d][x][y] + 2*(r-l+1) - (y-x+1));
                            x = y+1;
                        }
                    }
                    if (d<n-1){
                        for (int x=l; x<=r;){
                            if (A[d+1][x]) {x++; continue;}
                            int y = x; while (y<=r&&!A[d+1][y]) y++; y--;
                            _max(dp[u][d][l][r], dp[u][d+1][x][y] + 2*(r-l+1) - (y-x+1));
                            x = y+1;
                        }
                    }
                    //cout<<u<<' ' <<d<<' '<<l<<' '<<r<<' '<<dp[u][d][l][r]<<'\n';
                }
            }
        }
    }
    int ans = 0;
    for (int rw=0; rw<n; rw++){
        for (int l=0; l<n; l++){
            for (int r=l; r<=n; r++){
                ans = max(ans, dp[rw][rw][l][r] - (r-l+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