# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1233471 | antonn | Soccer Stadium (IOI23_soccer) | C++20 | 0 ms | 0 KiB |
#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;
}