#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define eb emplace_back
using ll = long long;
using ii = pair<int, int>;
using iiii = tuple<int, int, int, int>;
int clr[2005][2005], clu[2005][2005], cld[2005][2005];
ii clrp[2005][2005], clrs[2005][2005], par[4000005];
ll ans, dp[4000005];
vector<iiii> get_maximal_rects(const int &N, const vector<vector<int> > &F) {
vector<iiii> cur_rects;
for (int i = 0; i < N; i++) {
for (int j = N - 1; j >= 0; j--) {
if (F[i][j] == 1) {
clr[i][j] = j;
} else if (j + 1 < N) {
clr[i][j] = clr[i][j + 1];
} else {
clr[i][j] = N;
}
if (F[i][j] == 1) {
clu[i][j] = i;
} else if (i > 0) {
clu[i][j] = clu[i - 1][j];
} else {
clu[i][j] = -1;
}
if (F[i][j] == 1) {
clrp[i][j] = mp(N, N);
} else if (i > 0) {
clrp[i][j] = min(clrp[i - 1][j], mp(clr[i][j], i));
} else {
clrp[i][j] = mp(clr[i][j], i);
}
}
}
for (int i = N - 1; i >= 0; i--) {
for (int j = 0; j < N; j++) {
if (F[i][j] == 1) {
cld[i][j] = i;
} else if (i + 1 < N) {
cld[i][j] = cld[i + 1][j];
} else {
cld[i][j] = N;
}
if (F[i][j] == 1) {
clrs[i][j] = mp(N, N);
} else if (i + 1 < N) {
clrs[i][j] = min(clrs[i + 1][j], mp(clr[i][j], i));
} else {
clrs[i][j] = mp(clr[i][j], i);
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (F[i][j] == 1 || (j != 0 && F[i][j - 1] == 0)) {
continue;
}
int l1 = clu[i][j] + 1;
int r1 = cld[i][j] - 1;
while (l1 <= r1) {
int b1, g1;
if (clu[l1][j] + 1 == l1) {
tie(b1, g1) = clrp[r1][j];
} else {
tie(b1, g1) = clrs[l1][j];
}
cur_rects.eb(l1, j, r1, b1 - 1);
// obstacle at (g1, b1)
if (b1 == N) {
break;
}
if (i < g1) {
r1 = g1 - 1;
} else if (i > g1) {
l1 = g1 + 1;
} else {
break;
}
}
}
}
return cur_rects;
}
vector<vector<int> > rotate(const int &N, const vector<vector<int> > &F) {
vector<vector<int> > G(N, vector<int>(N, 0));
for (int col = N - 1; col >= 0; col--) {
for (int row = 0; row < N; row++) {
G[row][col] = F[N - col - 1][row];
}
}
return G;
}
ii unpack(const int &N, const int &x) {
int r = x / N, c = x % N;
return mp(r, c);
}
int biggest_stadium(int N, vector<vector<int> > F) {
vector<iiii> all_rects;
vector<vector<int> > H(N, vector<int>(N, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
H[i][j] = i * N + j;
}
}
for (int rep = 0; rep < 2; rep++) {
auto cur_rects = get_maximal_rects(N, F);
for (auto [r1, c1, r2, c2] : cur_rects) {
auto [nr1, nc1] = unpack(N, H[r1][c1]);
auto [nr2, nc2] = unpack(N, H[r2][c2]);
all_rects.eb(min(nr1, nr2), min(nc1, nc2), max(nr1, nr2), max(nc1, nc2));
}
F = rotate(N, F);
H = rotate(N, H);
}
sort(all_rects.begin(), all_rects.end(), [](const auto &lhs, const auto &rhs) {
auto [r11, c11, r12, c12] = lhs;
auto [r21, c21, r22, c22] = rhs;
return c12 - c11 > c22 - c21;
});
all_rects.erase(unique(all_rects.begin(), all_rects.end()), all_rects.end());
for (int i = 0; i < (int)all_rects.size(); i++) {
auto [r11, c11, r12, c12] = all_rects[i];
for (int j = 0; j < i; j++) {
auto [r21, c21, r22, c22] = all_rects[j];
if (c21 <= c11 && c12 <= c22 && r11 <= r21 && r22 <= r12) {
dp[i] = max(dp[i], dp[j] + (ll)((c22 - c21 + 1) - (c12 - c11 + 1)) * (r22 - r21 + 1));
}
}
ans = max(ans, dp[i] + (ll)(r12 - r11 + 1) * (c12 - c11 + 1));
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
1 ms |
604 KB |
ok |
| 4 |
Correct |
0 ms |
604 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Correct |
1 ms |
440 KB |
ok |
| 7 |
Correct |
2 ms |
2908 KB |
ok |
| 8 |
Correct |
24 ms |
21864 KB |
ok |
| 9 |
Correct |
364 ms |
181264 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
1 ms |
344 KB |
ok |
| 4 |
Correct |
0 ms |
348 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
440 KB |
ok |
| 7 |
Correct |
0 ms |
348 KB |
ok |
| 8 |
Correct |
0 ms |
348 KB |
ok |
| 9 |
Correct |
0 ms |
348 KB |
ok |
| 10 |
Correct |
0 ms |
348 KB |
ok |
| 11 |
Correct |
0 ms |
344 KB |
ok |
| 12 |
Correct |
0 ms |
348 KB |
ok |
| 13 |
Correct |
0 ms |
348 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
1 ms |
344 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
348 KB |
ok |
| 7 |
Correct |
0 ms |
440 KB |
ok |
| 8 |
Correct |
0 ms |
348 KB |
ok |
| 9 |
Correct |
0 ms |
348 KB |
ok |
| 10 |
Correct |
0 ms |
348 KB |
ok |
| 11 |
Correct |
0 ms |
348 KB |
ok |
| 12 |
Correct |
0 ms |
344 KB |
ok |
| 13 |
Correct |
0 ms |
348 KB |
ok |
| 14 |
Correct |
0 ms |
348 KB |
ok |
| 15 |
Runtime error |
1457 ms |
2097152 KB |
Execution killed with signal 9 |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
1 ms |
604 KB |
ok |
| 5 |
Correct |
0 ms |
604 KB |
ok |
| 6 |
Correct |
1 ms |
344 KB |
ok |
| 7 |
Correct |
0 ms |
348 KB |
ok |
| 8 |
Correct |
0 ms |
348 KB |
ok |
| 9 |
Correct |
0 ms |
440 KB |
ok |
| 10 |
Correct |
0 ms |
348 KB |
ok |
| 11 |
Correct |
0 ms |
348 KB |
ok |
| 12 |
Correct |
0 ms |
348 KB |
ok |
| 13 |
Correct |
0 ms |
348 KB |
ok |
| 14 |
Correct |
0 ms |
344 KB |
ok |
| 15 |
Correct |
0 ms |
348 KB |
ok |
| 16 |
Correct |
0 ms |
348 KB |
ok |
| 17 |
Runtime error |
1457 ms |
2097152 KB |
Execution killed with signal 9 |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
1 ms |
604 KB |
ok |
| 5 |
Correct |
0 ms |
604 KB |
ok |
| 6 |
Correct |
1 ms |
344 KB |
ok |
| 7 |
Correct |
0 ms |
348 KB |
ok |
| 8 |
Correct |
0 ms |
348 KB |
ok |
| 9 |
Correct |
0 ms |
440 KB |
ok |
| 10 |
Correct |
0 ms |
348 KB |
ok |
| 11 |
Correct |
0 ms |
348 KB |
ok |
| 12 |
Correct |
0 ms |
348 KB |
ok |
| 13 |
Correct |
0 ms |
348 KB |
ok |
| 14 |
Correct |
0 ms |
344 KB |
ok |
| 15 |
Correct |
0 ms |
348 KB |
ok |
| 16 |
Correct |
0 ms |
348 KB |
ok |
| 17 |
Runtime error |
1457 ms |
2097152 KB |
Execution killed with signal 9 |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
1 ms |
604 KB |
ok |
| 5 |
Correct |
0 ms |
604 KB |
ok |
| 6 |
Correct |
0 ms |
348 KB |
ok |
| 7 |
Correct |
1 ms |
440 KB |
ok |
| 8 |
Correct |
2 ms |
2908 KB |
ok |
| 9 |
Correct |
24 ms |
21864 KB |
ok |
| 10 |
Correct |
364 ms |
181264 KB |
ok |
| 11 |
Correct |
1 ms |
344 KB |
ok |
| 12 |
Correct |
0 ms |
348 KB |
ok |
| 13 |
Correct |
0 ms |
348 KB |
ok |
| 14 |
Correct |
0 ms |
440 KB |
ok |
| 15 |
Correct |
0 ms |
348 KB |
ok |
| 16 |
Correct |
0 ms |
348 KB |
ok |
| 17 |
Correct |
0 ms |
348 KB |
ok |
| 18 |
Correct |
0 ms |
348 KB |
ok |
| 19 |
Correct |
0 ms |
344 KB |
ok |
| 20 |
Correct |
0 ms |
348 KB |
ok |
| 21 |
Correct |
0 ms |
348 KB |
ok |
| 22 |
Runtime error |
1457 ms |
2097152 KB |
Execution killed with signal 9 |
| 23 |
Halted |
0 ms |
0 KB |
- |
