| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1059766 | aykhn | Soccer Stadium (IOI23_soccer) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "soccer.h"
using namespace std;
int n;
vector<vector<int>> A;
int dp[31][31][31][31];
int cur;
int f(int i, int pos, int l, int r)
{
if (i < 0 || i >= n) return 0;
if (l > r) return 0;
if (pos >= n) return 0;
if (dp[i][pos][l][r] != -1) return dp[i][pos][l][r];
vector<int> v;
v.push_back(l - 1);
for (int j = l; j <= r; j++) if (A[i][j]) v.push_back(j);
v.push_back(r + 1);
int res = 0;
for (int j = 1; j < v.size(); j++)
{
if (i <= cur)
{
res = max(res, f(i - 1, pos + 1, v[j - 1] + 1, v[j] - 1) + (v[j] - v[j - 1] - 1));
res = max(res, f(cur + (pos - (cur - i)) + 1, pos + 1, v[j - 1] + 1, v[j] - 1) + (v[j] - v[j - 1] - 1));
}
else
{
res = max(res, f(i + 1, pos + 1, v[j - 1] + 1, v[j] - 1) + (v[j] - v[j - 1] - 1));
res = max(res, f(cur - (pos - (i - cur)) - 1, pos + 1, v[j - 1] + 1, v[j] - 1) + (v[j] - v[j - 1] - 1));
}
}
return dp[i][pos][l][r] = res;
}
int solve()
{
for (int i = 0; i < 31; i++)
{
for (int j = 0; j < 31; j++)
{
for (int k = 0; k < 31; k++)
{
for (int l = k; l < 31; l++) dp[i][j][k][l] = -1;
}
}
}
return f(cur, 0, 0, n - 1);
}
int calc(int i, int j)
{
return i * n + j * n - i * j;
}
int biggest_stadium(int N, vector<vector<int>> B)
{
n = N;
A = B;
int c = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
c += A[i][j];
}
}
if (c == 1)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (A[i][j])
{
int i1 = n - i - 1, j1 = n - j - 1;
return max({calc(i, j), calc(i1, j), calc(i, j1), calc(i1, j1)});
}
}
}
}
int ok = 1, c1 = 0;
int l[N], r[N], cnt[N];
array<int, 2> mx = {-1, -1};
for (int i = 0; i < n; i++)
{
cnt[i] = 0;
l[i] = n + 1, r[i] = -1;
for (int j = 0; j < n; j++)
{
if (A[i][j]) continue;
cnt[i]++,
l[i] = min(l, j), r[i] = max(r, j);
}
if (!cnt[i]) continue;
if (cnt[i] != r - l + 1) ok = 0;
c1++;
mx = max(mx, {cnt[i], i});
}
if (ok)
{
int lx = mx[1], rx = mx[1];
int last = mx[1];
while (lx >= 0 || rx < N)
{
if (cnt[lx] && lx >= 0 && (rx == N || cnt[lx] <= cnt[rx]))
{
if (!(l[last] <= l[lx] && r[lx] <= r[last]))
{
ok = 0;
break;
}
last = lx;
lx--;
}
else if (cnt[rx] && rx < N && (lx == -1 || cnt[rx] <= cnt[lx]))
{
if (!(l[last] <= l[rx] && r[rx] <= r[last]))
{
ok = 0;
break;
}
last = rx;
rx++;
}
}
if (rx - lx - 1 == c1 && ok)
{
return n * n - c;
}
}
int res = 0;
for (cur = 0; cur < n; cur++)
{
res = max(res, solve());
}
return res;
}