Submission #1158602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158602		The_Samurai	Soccer Stadium (IOI23_soccer)	C++20	0 / 100	4593 ms	1748 KiB

soccer

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

struct dsu {
    vector<int> p, size;

    void init(int n) {
        p.assign(n + 1, 0);
        size.assign(n + 1, 1);
        for (int i = 1; i <= n; i++) p[i] = i;
    }

    int get(int a) {
        return (p[a] == a ? a : p[a] = get(p[a]));
    }

    void add(int a, int b) {
        a = get(a);
        b = get(b);
        if (a == b) return;
        if (size[a] > size[b]) swap(a, b);
        size[b] += size[a];
        p[a] = b;
    }
};

void maxs(int &a, int b) {
    if (a < b) a = b;
}

int biggest_stadium(int n, std::vector<std::vector<int>> a) {
    vector<vector<pair<int, int>>> ranges(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j]) continue;
            if (ranges[i].empty() or ranges[i].back().second + 1 < j) {
                ranges[i].emplace_back(j, j);
            } else {
                ranges[i].back().second++;
            }
        }
    }

    map<tuple<int, int, bool>, int> mp;
    for (int x = 0; x < n; x++) {
        if (ranges[x].empty()) continue;

        if (mp.empty()) {
            for (auto [l, r]: ranges[x]) {
                for (int i = l; i <= r; i++) for (int j = i; j <= r; j++) {
                    mp[{i, j, false}] = mp[{i, j, true}] = j - i + 1;
                }
            }
            continue;
        }

        map<tuple<int, int, bool>, int> nw;
        for (auto [l, r]: ranges[x]) {
            for (int i = l; i <= r; i++) for (int j = i; j <= r; j++) {
                nw[{i, j, false}] = nw[{i, j, true}] = j - i + 1;
                int ln = j - i + 1;
                for (auto [it, val]: mp) {
                    auto [l2, r2, tp] = it;

                    if (tp) {
                        // opening -> opening
                        if (i <= l2 and r2 <= j) maxs(nw[{i, j, true}], val + ln);
                    }

                    // opening/closing -> closing
                    if (!(l2 <= i and j <= r2)) continue;
                    maxs(nw[{i, j, false}], val + ln);
                }
            }
        }
        swap(nw, mp);
    }
    int ans = 0;
    for (auto [it, val]: mp) ans = max(ans, val);
    return ans;
}

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