Submission #845954

#	Time	Username	Problem	Language	Result	Execution time	Memory
845954		vjudge1	Soccer Stadium (IOI23_soccer)	C++17	25 / 100	243 ms	31852 KiB

soccer

#include "soccer.h"

#include <bits/stdc++.h>
// 123

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
        std::vector<std::pair<int, int>> segs(N, {-1, -1});
        int sum = 0;
        int k = -1, best = -1;
        for (int i = 0; i < N; i++) {
                int cnt = 0;
                int l = N, r = -1;
                for (int j = 0; j < N; j++) {
                        if (F[i][j] == 0) {
                                cnt++;
                                l = std::min(l, j);
                                r = std::max(r, j);
                        }
                }
                if (cnt) {
                        if (r - l + 1 != cnt) return 0;
                        segs[i] = {l, r};
                        sum += cnt;
                        if (r - l > best) {
                                best = r - l;
                                k = i;
                        }
                }
        }
        int l = k, r = k;
        int ll = segs[k].first, rr = segs[k].second;
        int cur = rr - ll + 1;
        while (true) {
                if (l == 0 || segs[l - 1].first == -1) {
                        if (r == N - 1) break;
                        if (segs[r + 1].first == -1) break;
                        auto [nl, nr] = segs[r + 1];
                        if (nl < ll || nr > rr) return 0;
                        ll = nl, rr = nr;
                        cur += nr - nl + 1;
                        r++;
                } else if (r == N - 1 || segs[r + 1].first == -1) {
                        if (segs[l - 1].first == -1) break;
                        auto [nl, nr] = segs[l - 1];
                        if (nl < ll || nr > rr) return 0;
                        ll = nl, rr = nr;
                        cur += nr - nl + 1;
                        l--;
                } else {
                        auto [ul, ur] = segs[l - 1];
                        auto [dl, dr] = segs[r + 1];
                        if (ur - ul > dr - dl) {
                                l--;
                                if (ul < ll || ur > rr) return 0;
                                ll = ul, rr = ur;
                                cur += ur - ul + 1;
                        } else {
                                r++;
                                if (dl < ll || dr > rr) return 0;
                                ll = dl, rr = dr;
                                cur += dr - dl + 1;
                        }
                }
        }
        return cur == sum ? sum : 0;
}

• 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