#include "soccer.h"
#include "bits/stdc++.h"
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
using namespace std;
using dp_t = vector<vector<vector<int>>>;
bool allPos = true;
int su = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
su += F[i][j];
}
}
if (su == 1) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (F[i][j] == 1) {
return N * N - min(i + 1, N - i) * min(j + 1, N - j);
}
}
}
} else {
vector<pair<int, int>> ra(N);
vector<int> les(N);
for (int i = 0; i < N; ++i) {
ra[i].first = 0;
for (; ra[i].first < N; ra[i].first++) {
if (F[i][ra[i].first] == 0) break;
}
ra[i].second = N - 1;
for (; ra[i].second >= 0; ra[i].second--) {
if (F[i][ra[i].second] == 0) break;
}
les[i] = ra[i].second - ra[i].first + 1;
for (int j = ra[i].first; j <= ra[i].second; ++j) {
if (F[i][j] == 1) allPos = false;
}
if (!allPos) break;
}
int tot = 0;
int maI = max_element(les.begin(), les.end()) - les.begin();
pair<int, int> actRa = ra[maI];
pair<int, int> oRa = {maI, maI};
tot = les[maI];
while (allPos && oRa != make_pair(0, N - 1)) {
int ne = oRa.first - 1;
if (ne < 0 || (oRa.second < N - 1 && les[ne] < les[oRa.second + 1])) ne = oRa.second + 1;
if (les[ne] < 0) break;
if (actRa.first > ra[ne].first || actRa.second < ra[ne].second) allPos = false;
actRa = ra[ne];
tot += les[ne];
oRa = {min(oRa.first, ne), max(oRa.second, ne)};
}
if (allPos) return tot;
else if (N > 500) return 0;
else {
vector<vector<int>> prefS(N, vector<int>(N + 1, 0));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
prefS[i][j + 1] = prefS[i][j] + F[i][j];
}
}
dp_t dpU(N + 1, vector<vector<int>>(N + 1, vector<int>(N + 1, -N * N)));
auto dpD = dpU;
int ma = 0;
for (int i = 0; i <= N; ++i) {
for (int j = N - 1; j >= 0; --j) {
for (int k = j + 1; k <= N; ++k) {
if (i == 0)dpU[0][j][k] = 0;
else if (prefS[i - 1][k + 1] - prefS[i - 1][j - 1] == 0) dpU[i][j][k] = dpU[i - 1][j][k] + k - j + 1;
else dpU[i][j][k] = max(dpU[i][j][k - 1], dpU[i][j + 1][k]);
}
}
}
for (int i = N; i >= 0; ++i) {
for (int j = N - 1; j >= 0; --j) {
for (int k = j + 1; k <= N; ++k) {
if (i == N) dpD[N][j][k] = 0;
else if (prefS[i][k + 1] - prefS[i][j - 1] == 0) {
dpD[i][j][k] = dpD[i + 1][j][k] + k - j + 1;
ma = max(ma, dpD[i][j][k] + dpU[i + 1][j][k]);
}
else dpD[i][j][k] = max(dpD[i][j][k - 1], dpD[i][j + 1][k]);
}
}
}
return ma;
}
}
}
Compilation message
soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:91:1: warning: control reaches end of non-void function [-Wreturn-type]
91 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
436 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
0 ms |
348 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
348 KB |
ok |
| 7 |
Correct |
1 ms |
348 KB |
ok |
| 8 |
Correct |
13 ms |
2908 KB |
ok |
| 9 |
Correct |
199 ms |
35152 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
436 KB |
ok |
| 3 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
