#include <iostream>
#include <vector>
using namespace std;
const int N = 30;
int n;
int tree[2000][2000];
int prefix[N][N];
int dp1[N][N][N];
int dp2[N][N][N];
int dp3[N][N][N];
int dp4[N][N][N];
bool are_empty(int row, int col1, int col2) {
if (col1 == 0) {
return prefix[row][col2] == 0;
}
return prefix[row][col2] == prefix[row][col1 - 1];
}
int solve_1() {
int x = 0;
int y = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (tree[i][j] == 1) {
x = i;
y = j;
}
}
}
x += 1;
y += 1;
int m = x * y;
int t = x * (n - y + 1);
if (t < m) {
m = t;
}
t = (n - x + 1) * y;
if (t < m) {
m = t;
}
t = (n - x + 1) * (n - y + 1);
if (t < m) {
m = t;
}
return n * n - m;
}
// int biggest_stadium(int N, int[][] F)
int biggest_stadium(int X, vector<vector<int>> F) {
n = X;
int total = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
tree[i][j] = F[i][j];
total += tree[i][j];
}
}
if (total == 1) {
return solve_1();
}
if (total == 0) {
return n * n;
}
if (n > 30) {
return 123;
}
// init
for (int i = 0; i < n; i++) {
prefix[i][0] = tree[i][0];
for (int j = 1; j < n; j++) {
prefix[i][j] = prefix[i][j - 1] + tree[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
dp1[i][j][k] = -1;
dp2[i][j][k] = -1;
dp3[i][j][k] = -1;
dp4[i][j][k] = -1;
}
}
}
for (int j = 0; j < n; j++) {
for (int k = j; k < n; k++) {
// if all empty
if (are_empty(0, j, k)) {
dp1[0][j][k] = k - j + 1;
dp2[0][j][k] = k - j + 1;
dp3[0][j][k] = k - j + 1;
dp4[0][j][k] = k - j + 1;
}
}
}
// dp from 1 to n - 1
for (int i = 1; i < n; i++) {
// cout << i << "\n";
for (int j = 0; j < n; j++) {
for (int k = j; k < n; k++) {
// check base case
if (are_empty(i, j, k)) {
dp1[i][j][k] = k - j + 1;
dp2[i][j][k] = k - j + 1;
dp3[i][j][k] = k - j + 1;
dp4[i][j][k] = k - j + 1;
} else {
continue;
}
for (int l = 0; l < n; l++) {
for (int m = l; m < n; m++) {
// check if [l, m] are all empty
if (!are_empty(i - 1, l, m)) {
break;
}
// check if [j, k] overlaps with [l, m]
if (k < l || j > m) {
continue;
}
// dp1
if (j <= l && k >= m) {
if (dp1[i - 1][l][m] != -1) {
int t = dp1[i - 1][l][m] + k - j + 1;
if (dp1[i][j][k] == -1 || dp1[i][j][k] < t) {
dp1[i][j][k] = t;
}
}
}
// dp2
if (j >= l && k >= m) {
int t = dp1[i - 1][l][m];
if (t == -1 || t < dp2[i - 1][l][m]) {
t = dp2[i - 1][l][m];
}
if (t != -1 && (dp2[i][j][k] == -1 || dp2[i][j][k] < t + k - j + 1)) {
dp2[i][j][k] = t + k - j + 1;
}
}
// dp3
if (j <= l && k <= m) {
int t = dp1[i - 1][l][m];
if (t == -1 || t < dp3[i - 1][l][m]) {
t = dp3[i - 1][l][m];
}
if (t != -1 && (dp3[i][j][k] == -1 || dp3[i][j][k] < t + k - j + 1)) {
dp3[i][j][k] = t + k - j + 1;
}
}
// dp4
if (j >= l && k <= m) {
int t = dp1[i - 1][l][m];
if (t == -1 || t < dp2[i - 1][l][m]) {
t = dp2[i - 1][l][m];
}
if (t == -1 || t < dp3[i - 1][l][m]) {
t = dp3[i - 1][l][m];
}
if (t == -1 || t < dp4[i - 1][l][m]) {
t = dp4[i - 1][l][m];
}
if (t != -1 && (dp4[i][j][k] == -1 || dp4[i][j][k] < t + k - j + 1)) {
dp4[i][j][k] = t + k - j + 1;
}
}
}
}
}
}
}
/*for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = j; k < n; k++) {
cout << i << " " << j << " " << k << " " << dp1[i][j][k] << "\n";
}
}
}*/
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (ans < dp1[i][j][k]) {
ans = dp1[i][j][k];
}
if (ans < dp2[i][j][k]) {
ans = dp2[i][j][k];
}
if (ans < dp3[i][j][k]) {
ans = dp3[i][j][k];
}
if (ans < dp4[i][j][k]) {
ans = dp4[i][j][k];
}
}
}
}
// cout << ans << "\n";
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
ok |
| 2 |
Correct |
0 ms |
212 KB |
ok |
| 3 |
Correct |
0 ms |
340 KB |
ok |
| 4 |
Correct |
0 ms |
340 KB |
ok |
| 5 |
Correct |
0 ms |
212 KB |
ok |
| 6 |
Correct |
1 ms |
212 KB |
ok |
| 7 |
Correct |
1 ms |
724 KB |
ok |
| 8 |
Correct |
17 ms |
5204 KB |
ok |
| 9 |
Correct |
280 ms |
47388 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
ok |
| 2 |
Correct |
0 ms |
212 KB |
ok |
| 3 |
Correct |
1 ms |
340 KB |
ok |
| 4 |
Correct |
0 ms |
340 KB |
ok |
| 5 |
Incorrect |
0 ms |
340 KB |
wrong |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
ok |
| 2 |
Correct |
0 ms |
212 KB |
ok |
| 3 |
Correct |
0 ms |
212 KB |
ok |
| 4 |
Correct |
1 ms |
340 KB |
ok |
| 5 |
Correct |
0 ms |
340 KB |
ok |
| 6 |
Incorrect |
0 ms |
340 KB |
wrong |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
ok |
| 2 |
Correct |
0 ms |
212 KB |
ok |
| 3 |
Correct |
0 ms |
212 KB |
ok |
| 4 |
Correct |
0 ms |
340 KB |
ok |
| 5 |
Correct |
0 ms |
340 KB |
ok |
| 6 |
Correct |
1 ms |
340 KB |
ok |
| 7 |
Correct |
0 ms |
340 KB |
ok |
| 8 |
Incorrect |
0 ms |
340 KB |
wrong |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
ok |
| 2 |
Correct |
0 ms |
212 KB |
ok |
| 3 |
Correct |
0 ms |
212 KB |
ok |
| 4 |
Correct |
0 ms |
340 KB |
ok |
| 5 |
Correct |
0 ms |
340 KB |
ok |
| 6 |
Correct |
1 ms |
340 KB |
ok |
| 7 |
Correct |
0 ms |
340 KB |
ok |
| 8 |
Incorrect |
0 ms |
340 KB |
wrong |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
ok |
| 2 |
Correct |
0 ms |
212 KB |
ok |
| 3 |
Correct |
0 ms |
212 KB |
ok |
| 4 |
Correct |
0 ms |
340 KB |
ok |
| 5 |
Correct |
0 ms |
340 KB |
ok |
| 6 |
Correct |
0 ms |
212 KB |
ok |
| 7 |
Correct |
1 ms |
212 KB |
ok |
| 8 |
Correct |
1 ms |
724 KB |
ok |
| 9 |
Correct |
17 ms |
5204 KB |
ok |
| 10 |
Correct |
280 ms |
47388 KB |
ok |
| 11 |
Correct |
1 ms |
340 KB |
ok |
| 12 |
Correct |
0 ms |
340 KB |
ok |
| 13 |
Incorrect |
0 ms |
340 KB |
wrong |
| 14 |
Halted |
0 ms |
0 KB |
- |
