Submission #841078

#	Time	Username	Problem	Language	Result	Execution time	Memory
841078		Lucpp	Soccer Stadium (IOI23_soccer)	C++17	64 / 100	4567 ms	63336 KiB

soccer

#include <bits/stdc++.h>
#include "soccer.h"
using namespace std;

int biggest_stadium(int N, vector<vector<int>> F){
    int ans = 0;
    for(int k = 0; k < N; k++){
        vector<int> l(N, k), r(N, k);
        for(int i = 0; i < N; i++){
            if(F[i][k]) continue;
            while(l[i] > 0 && F[i][l[i]-1] == 0) l[i]--;
            while(r[i] < N && F[i][r[i]] == 0) r[i]++;
        }
        vector<vector<int>> score(N, vector<int>(N));
        for(int i = 0; i < N; i++){
            int mal = 0, mir = N;
            for(int j = i; j < N; j++){
                mal = max(mal, l[j]);
                mir = min(mir, r[j]);
                score[i][j] = max(0, mir-mal);
            }
        }
        vector<vector<int>> dp(N, vector<int>(N));
        for(int d = N-1; d >= 0; d--){
            for(int i = 0; i+d < N; i++){
                int j = i+d;
                int res = 0;
                if(i > 0) res = dp[i-1][j] + score[i-1][j];
                if(j < N-1) res = max(res, dp[i][j+1] + score[i][j+1]);
                dp[i][j] = res;
            }
        }
        for(int i = 0; i < N; i++) ans = max(ans, dp[i][i]+score[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: 16 / 16
• Subtask 6: 0 / 30