| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1064058 | DorostWef | 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 "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 504, INF = -5000000;
vector <int> a[N][N];
int dp[N][N][N];
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
if (N >= 501) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (F[i][j]) {
int mx = min ({(i + 1) * (j + 1), (i + 1) * (n - j), (n - i) * (j + 1), (n - i) * (n - j)});
return n * n - mx;
}
}
}
}
int mx = 0;
int n = N;
for (int l = n - 1; l >= 0; l--) {
for (int r = l; r < n; r++) {
if (l != r) {
a[l][r] = a[l + 1][r];
}
for (int j = 0; j < n; j++) {
if (F[l][j])
a[l][r].push_back(j);
}
a[l][r].push_back(-1);
a[l][r].push_back(n);
sort (a[l][r].begin(), a[l][r].end());
a[l][r].erase (unique (a[l][r].begin(), a[l][r].end()), a[l][r].end());
for (int k = 0; k < (int)a[l][r].size() - 1; k++) {
int L = a[l][r][k];
int R = a[l][r][k + 1];
int s = R - L - 1;
if (L != -1) {
dp[l][r][L] = INF;
}
for (int w = L + 1; w < R; w++) {
int mm = 0;
if (l != r) {
mm = max (dp[l + 1][r][w], dp[l][r - 1][w]);
}
dp[l][r][w] = s + mm;
//cout << l << ' ' << r << ' ' << L << ' ' << R << endl;
mx = max (mx, dp[l][r][w]);
}
}
}
}
return mx;
}