Submission #847320

#	Time	Username	Problem	Language	Result	Execution time	Memory
847320		Lucpp	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	565 ms	95060 KiB

soccer

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

int biggest_stadium(int N, vector<vector<int>> F){
    vector<vector<int>> L(N, vector<int>(N)), R(N, vector<int>(N, N)), H(N, vector<int>(N));
    vector<vector<int>> dp(N, vector<int>(N));
    int ans = 0;
    for(int i = 0; i < N; i++){
        if(i > 0) H[i] = H[i-1];
        for(int j = 0; j < N; j++){
            if(F[i][j]) H[i][j] = 0;
            else H[i][j]++;
        }
        stack<pair<int, int>> s;
        s.emplace(-1, -1);
        for(int k = 0; k < N; k++){
            while(s.top().first > H[i][k]){
                R[i][s.top().second] = k;
                s.pop();
            }
            if(s.top().first == H[i][k]) L[i][k] = L[i][s.top().second];
            else L[i][k] = s.top().second+1;
            s.emplace(H[i][k], k);
        }
        vector<int> ord(N);
        for(int j = 0; j < N; j++) ord[j] = j;
        sort(ord.begin(), ord.end(), [&](int a, int b){return H[i][a]<H[i][b];});
        for(int j : ord){
            if(H[i][j] == 0) continue;
            int w = R[i][j]-L[i][j];
            dp[i][j] = w*H[i][j];
            if(i > 0) dp[i][j] = max(dp[i][j], w+dp[i-1][j]);
            if(int k = L[i][j]-1; k >= 0){
                dp[i][j] = max(dp[i][j], w*(H[i][j]-H[i][k]) + dp[i][k]);
            }
            if(int k = R[i][j]; k < N){
                dp[i][j] = max(dp[i][j], w*(H[i][j]-H[i][k]) + dp[i][k]);
            }
            ans = max(ans, dp[i][j]);
        }
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 16 / 16
• Subtask 6: 30 / 30