#include "soccer.h"
#include <iostream>
#include <complex>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
#include <cstdint>
#include <cassert>
using namespace std;
int biggest_stadium(int n, std::vector<std::vector<int>> f)
{
vector <vector<int>> A(n, vector <int> (n, 0)),
B(n, vector <int> (n, 0));
for(int i = 0; i < n; i++){
int last = -1;
for(int j = 0; j < n; j++){
if(f[i][j] == 1) last = j;
A[i][j] = last;
}
last = n;
for(int j = n-1; j >= 0; j--){
if(f[i][j] == 1) last = j;
B[i][j] = last;
}
}
//vector <vector<vector<int>>> dp1(n + 1, vector <vector<int>>
// (n + 1, vector <int> (n + 1, -1)));
//vector <vector<vector<int>>> dp2(n + 1, vector <vector<int>>
// (n + 1, vector <int> (n + 1, -1)));
int dp[10][10][10][10][10][10] = { };
auto F = [&](auto F, int i, int j, int a, int b, int c, int d) -> int
{
if(dp[i][j][a][b][c][d] != 0) return dp[i][j][a][b][c][d];
dp[i][j][a][b][c][d] = (b - a + 1);
if(i != j) dp[i][j][a][b][c][d] += (d - c + 1);
int mx = 0;
if(i != 0)
{
for(int k = a; k <= b; k++) if(f[i-1][k] == 0)
{
int l1 = max(A[i-1][k]+1, a), r1 = min(B[i-1][k]-1, b);
int l2 = max(c, l1), r2 = min(d, r1);
mx = max(mx, F(F, i-1, j, l1, r1, l2, r2) - (r2 - l2 + 1));
}
}
if(j != n-1)
{
for(int k = c; k <= d; k++) if(f[j+1][k] == 0)
{
int l2 = max(A[j+1][k]+1, c), r2 = min(B[j+1][k]-1, d);
int l1 = max(a, l2), r1 = min(b, r2);
mx = max(mx, F(F, i, j+1, l1, r1, l2, r2) - (r1 - l1 + 1));
}
}
return dp[i][j][a][b][c][d] = (dp[i][j][a][b][c][d] + mx);
};
int ans = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
int l = A[i][j]+1, r = B[i][j]-1;
ans = max(ans, F(F, i, i, l, r, l, r));
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4440 KB |
ok |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4188 KB |
ok |
2 |
Correct |
3 ms |
4188 KB |
ok |
3 |
Correct |
3 ms |
4188 KB |
ok |
4 |
Correct |
2 ms |
4188 KB |
ok |
5 |
Correct |
2 ms |
4188 KB |
ok |
6 |
Correct |
2 ms |
4188 KB |
ok |
7 |
Runtime error |
6 ms |
8796 KB |
Execution killed with signal 11 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4188 KB |
ok |
2 |
Correct |
3 ms |
4188 KB |
ok |
3 |
Correct |
2 ms |
4188 KB |
ok |
4 |
Correct |
3 ms |
4188 KB |
ok |
5 |
Correct |
3 ms |
4188 KB |
ok |
6 |
Correct |
2 ms |
4188 KB |
ok |
7 |
Correct |
2 ms |
4188 KB |
ok |
8 |
Correct |
3 ms |
4276 KB |
ok |
9 |
Correct |
2 ms |
4188 KB |
ok |
10 |
Correct |
2 ms |
4188 KB |
ok |
11 |
Correct |
2 ms |
4188 KB |
ok |
12 |
Correct |
2 ms |
4188 KB |
ok |
13 |
Correct |
2 ms |
4188 KB |
ok |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4440 KB |
ok |
2 |
Correct |
3 ms |
4188 KB |
ok |
3 |
Correct |
3 ms |
4188 KB |
ok |
4 |
Correct |
2 ms |
4188 KB |
ok |
5 |
Correct |
3 ms |
4188 KB |
ok |
6 |
Correct |
3 ms |
4188 KB |
ok |
7 |
Correct |
2 ms |
4188 KB |
ok |
8 |
Correct |
2 ms |
4188 KB |
ok |
9 |
Correct |
3 ms |
4276 KB |
ok |
10 |
Correct |
2 ms |
4188 KB |
ok |
11 |
Correct |
2 ms |
4188 KB |
ok |
12 |
Correct |
2 ms |
4188 KB |
ok |
13 |
Correct |
2 ms |
4188 KB |
ok |
14 |
Correct |
2 ms |
4188 KB |
ok |
15 |
Correct |
2 ms |
4188 KB |
ok |
16 |
Correct |
2 ms |
4188 KB |
ok |
17 |
Correct |
2 ms |
4188 KB |
ok |
18 |
Correct |
3 ms |
4188 KB |
ok |
19 |
Correct |
3 ms |
4188 KB |
ok |
20 |
Correct |
2 ms |
4188 KB |
ok |
21 |
Correct |
3 ms |
4188 KB |
ok |
22 |
Correct |
2 ms |
4188 KB |
ok |
23 |
Correct |
3 ms |
4188 KB |
ok |
24 |
Correct |
3 ms |
4184 KB |
ok |
25 |
Correct |
2 ms |
4188 KB |
ok |
26 |
Correct |
2 ms |
4188 KB |
ok |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4440 KB |
ok |
2 |
Correct |
3 ms |
4188 KB |
ok |
3 |
Correct |
3 ms |
4188 KB |
ok |
4 |
Correct |
3 ms |
4188 KB |
ok |
5 |
Correct |
2 ms |
4188 KB |
ok |
6 |
Correct |
2 ms |
4188 KB |
ok |
7 |
Correct |
3 ms |
4188 KB |
ok |
8 |
Correct |
3 ms |
4188 KB |
ok |
9 |
Correct |
2 ms |
4188 KB |
ok |
10 |
Correct |
2 ms |
4188 KB |
ok |
11 |
Correct |
3 ms |
4276 KB |
ok |
12 |
Correct |
2 ms |
4188 KB |
ok |
13 |
Correct |
2 ms |
4188 KB |
ok |
14 |
Correct |
2 ms |
4188 KB |
ok |
15 |
Correct |
2 ms |
4188 KB |
ok |
16 |
Correct |
2 ms |
4188 KB |
ok |
17 |
Correct |
2 ms |
4188 KB |
ok |
18 |
Correct |
2 ms |
4188 KB |
ok |
19 |
Correct |
2 ms |
4188 KB |
ok |
20 |
Correct |
3 ms |
4188 KB |
ok |
21 |
Correct |
3 ms |
4188 KB |
ok |
22 |
Correct |
2 ms |
4188 KB |
ok |
23 |
Correct |
3 ms |
4188 KB |
ok |
24 |
Correct |
2 ms |
4188 KB |
ok |
25 |
Correct |
3 ms |
4188 KB |
ok |
26 |
Correct |
3 ms |
4184 KB |
ok |
27 |
Correct |
2 ms |
4188 KB |
ok |
28 |
Correct |
2 ms |
4188 KB |
ok |
29 |
Correct |
2 ms |
4184 KB |
ok |
30 |
Runtime error |
5 ms |
8484 KB |
Execution killed with signal 11 |
31 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4440 KB |
ok |
2 |
Correct |
3 ms |
4188 KB |
ok |
3 |
Correct |
3 ms |
4188 KB |
ok |
4 |
Correct |
3 ms |
4188 KB |
ok |
5 |
Correct |
2 ms |
4188 KB |
ok |
6 |
Correct |
2 ms |
4188 KB |
ok |
7 |
Correct |
3 ms |
4188 KB |
ok |
8 |
Correct |
3 ms |
4188 KB |
ok |
9 |
Correct |
2 ms |
4188 KB |
ok |
10 |
Correct |
2 ms |
4188 KB |
ok |
11 |
Correct |
3 ms |
4276 KB |
ok |
12 |
Correct |
2 ms |
4188 KB |
ok |
13 |
Correct |
2 ms |
4188 KB |
ok |
14 |
Correct |
2 ms |
4188 KB |
ok |
15 |
Correct |
2 ms |
4188 KB |
ok |
16 |
Correct |
2 ms |
4188 KB |
ok |
17 |
Correct |
2 ms |
4188 KB |
ok |
18 |
Correct |
2 ms |
4188 KB |
ok |
19 |
Correct |
2 ms |
4188 KB |
ok |
20 |
Correct |
3 ms |
4188 KB |
ok |
21 |
Correct |
3 ms |
4188 KB |
ok |
22 |
Correct |
2 ms |
4188 KB |
ok |
23 |
Correct |
3 ms |
4188 KB |
ok |
24 |
Correct |
2 ms |
4188 KB |
ok |
25 |
Correct |
3 ms |
4188 KB |
ok |
26 |
Correct |
3 ms |
4184 KB |
ok |
27 |
Correct |
2 ms |
4188 KB |
ok |
28 |
Correct |
2 ms |
4188 KB |
ok |
29 |
Correct |
2 ms |
4184 KB |
ok |
30 |
Runtime error |
5 ms |
8484 KB |
Execution killed with signal 11 |
31 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4440 KB |
ok |
2 |
Correct |
3 ms |
4188 KB |
ok |
3 |
Correct |
3 ms |
4188 KB |
ok |
4 |
Correct |
3 ms |
4188 KB |
ok |
5 |
Correct |
2 ms |
4188 KB |
ok |
6 |
Correct |
2 ms |
4188 KB |
ok |
7 |
Correct |
2 ms |
4188 KB |
ok |
8 |
Runtime error |
6 ms |
8796 KB |
Execution killed with signal 11 |
9 |
Halted |
0 ms |
0 KB |
- |