Submission #1059995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059995		tolbi	Soccer Stadium (IOI23_soccer)	C++17	48 / 100	4584 ms	6256 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    int ans = 0;
    for (int _ = 0; _ < N; _++){
        int left[N]={};
        int right[N]={};
        for (int j = 0; j < N; j++){
            for (int i = _+1; i < N; i++){
                if (!F[i][j]){
                    right[j]++;
                }
                else break;
            }
            for (int i = _; i >= 0; i--){
                if (!F[i][j]){
                    left[j]++;
                }
                else break;
            }
        }
        vector<vector<int>> minl(N,vector<int>(N));
        vector<vector<int>> minr(N,vector<int>(N));
        for (int i = 0; i < N; i++){
            minl[i][i]=left[i];
            minr[i][i]=right[i];
            for (int j = i+1; j < N; j++){
                minl[i][j]=min(minl[i][j-1],left[j]);
                minr[i][j]=min(minr[i][j-1],right[j]);
            }
        }
        for (int i = 0; i < N; i++){
            vector<vector<int>> dp(N,vector<int>(N,-1));
            function<int(int,int)> f = [&](int lef, int rig)->int{
                if (dp[lef][rig]!=-1) return dp[lef][rig];
                dp[lef][rig]=0;
                if (i-lef-1>=0){
                    //leftten al
                    int cur = minl[i-lef-1][i+rig]+minr[i-lef-1][i+rig];
                    dp[lef][rig]=max(dp[lef][rig],f(lef+1,rig)+cur);
                }
                if (i+rig+1<N) {
                    //righttan al
                    int cur = minl[i-lef][i+rig+1]+minr[i-lef][i+rig+1];
                    dp[lef][rig]=max(dp[lef][rig],f(lef,rig+1)+cur);
                }
                return dp[lef][rig];
            };
            ans=max(ans,f(0,0)+right[i]+left[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