Submission #1233473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233473		antonn	Soccer Stadium (IOI23_soccer)	C++20	1.50 / 100	214 ms	63228 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2000 + 7;
const int M = 30 + 7;

int a[N][N], pref[N][N];
int dp[M][M][M][M];

bool ok(int l, int x, int y) {
    return pref[l][y] - pref[l][x - 1] == 0;
}

int biggest_stadium(int n, vector<vector<int>> F) {
    bool full = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            a[i][j] = F[i - 1][j - 1];
            pref[i][j] = pref[i][j - 1] + a[i][j];
            if (a[i][j] == 0) full = 0;
        }
    }
    if (full) return 0;
    vector<pair<int, int>> p(n + 1);
    bool all = 1;
    int total = 0;
    for (int i = 1; i <= n; ++i) {
        int cnt = 0;
        int l = 1e9, r = 0;
        for (int j = 1; j <= n; ++j) {
            if (a[i][j] == 0) {
                ++cnt;
                l = min(l, j);
                r = max(r, j);
            }
        }
        p[i] = {l, r};
        if (cnt != 0 && r - l + 1 != cnt) {
            all = 0;
        } 
        total += cnt;
    }
    int lines = 0;
    for (int i = 1; i <= n; ++i) if (p[i].first != 1e9) lines++;
    int f = -1, l = -1;
    for (int i = 1; i <= n; ++i) {
        if (p[i].first != 1e9) {
            if (f == -1) f = i;
            l = i;
        }
    }
    if (l - f + 1 != lines) all = false;
    for (int i = f; i <= l; ++i) {
        for (int j = i; j <= l; ++j) {
            if (p[i].first <= p[j].first && p[j].second <= p[i].second) continue;
            if (p[j].first <= p[i].first && p[i].second <= p[j].second) continue;
            all = 0;
        }
    }
    if (all) return total;
    return -1;
}

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