#include <iostream>
#include <vector>
using namespace std;
const int N = 30;
int n;
int tree[N][N];
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 biggest_stadium(int N, int[][] F)
int biggest_stadium(int X, vector<vector<int>> F) {
n = X;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
tree[i][j] = F[i][j];
}
}
// 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;
}
}
}
// dp from 1 to n - 1
for (int i = 1; i < n; i++) {
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;
} 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 && (dp4[i][j][k] == -1 || dp4[i][j][k] < t + k - j + 1)) {
dp4[i][j][k] = t + k - j + 1;
}
}
}
}
}
}
}
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";
}
/*int main() {
cin >> n;
if (n > 30) {
cout << 123 << "\n";
return 0;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> tree[i][j];
}
}
solve();
return 0;
}*/
Compilation message
soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:142:1: warning: no return statement in function returning non-void [-Wreturn-type]
142 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
