Submission #1205812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205812		Pacybwoah	Soccer Stadium (IOI23_soccer)	C++20	25 / 100	250 ms	63384 KiB

soccer

#include "soccer.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
typedef long long ll;
int biggest_stadium(int N, std::vector<std::vector<int>> F){
    int n = N, ans = 0;
    vector<vector<int>> vec(n + 1, vector<int>(n + 1)), pre(n + 1, vector<int>(n + 1));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            vec[i][j] = 1 - F[i - 1][j - 1];
            ans += vec[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + vec[i][j];
        }
    }
    auto get = [&](int a, int b, int c, int d){
        // (a, b) -> (c, d)
        return pre[c][d] - pre[c][b - 1] - pre[a - 1][d] + pre[a - 1][b - 1];
    };
    vector<pair<int, pair<int, int>>> rngs;
    for(int i = 1; i <= n; i++){
        int mini = n + 1, maxi = 0;
        for(int j = 1; j <= n; j++){
            if(vec[i][j] == 1){
                mini = min(mini, j);
                maxi = max(maxi, j);
            }
        }
        if(mini > maxi) continue;
        if(get(i, mini, i, maxi) != maxi - mini + 1) return 0;
        rngs.emplace_back(i, make_pair(mini, maxi));
    }
    int sz = (int)rngs.size();
    for(int i = 0; i < sz; i++){
        for(int j = i + 1; j < sz; j++){
            auto &[l, r] = rngs[i].second;
            auto &[tl, tr] = rngs[j].second;
            int ul = max(l, tl), ur = min(r, tr);
            if((l != ul || r != ur) && (tl != ul || tr != ur)) return 0;
            int t = rngs[i].first, b = rngs[j].first;
            if(get(t, ul, b, ur) != (b - t + 1) * (ur - ul + 1)) return 0;
        }
    }
    return ans;
}

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