#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define ll long long int
// #define cerr if(0) cerr
const int N = 35, M = 3e5;
int arr[4][2] = {
{0, 1},
{0, -1},
{1, 0},
{-1, 0}
};
int dp[N][N][N][N][2], pref[N][N];
bitset<N> vis[N];
vector<pii> g[N][N];
int get(int row, int l, int r){
return pref[row][r] - (l == 0 ? 0 : pref[row][l - 1]);
}
int biggest_stadium(int n, std::vector<std::vector<int>> a)
{
int cnt = 0, px = 0, py = 0;
queue<pii> q;
bool any = false;
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if(a[i][j] == 0){
if(!any){
any = true;
q.push({i, j});
vis[i][j] = 1;
}
for(int k = 0; k < 4; ++k){
int nx = i + arr[k][0];
int ny = j + arr[k][1];
if(nx >= 0 && ny < n && ny >= 0 && nx < n && a[nx][ny] == 0){
g[i][j].pb({nx, ny});
}
}
}else{
++cnt;
px = i, py = j;
}
}
}
if(cnt == 0){
return n * n;
}
if(cnt == 1){
return n*n - min({
(px + 1) * (py + 1),
(px + 1) * (n - py),
(n - px) * (n - py),
(n - px) * (py + 1),
});
}
int ans = 1;
for(int i = 0; i < n; ++i){
pref[i][0] = a[i][0];
for(int j = 1; j < n; ++j) pref[i][j] = pref[i][j - 1] + a[i][j];
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if(a[i][j]) continue;
int L = j;
while(j < n && a[i][j] == 0) ++j;
--j;
int R = j;
// cerr << i << ' ' << L << ' ' << R << ":\n";
// we know l...r borders
for(int u = i; u >= 0; --u){
for(int d = i; d < n; ++d){
for(int len = R-L+1; len >= 1; --len){
for(int l = L; l + len - 1 <= R; ++l){
int r = l + len - 1;
if(u == i && d == i){
dp[u][d][l][r][0] = dp[u][d][l][r][1] = r - l + 1;
ans = max(ans, len);
continue;
}
if(get(u, l, r) || get(d, l, r)){
dp[u][d][l][r][0] = dp[u][d][l][r][1] = 0;
continue;
}
if(u == i){
dp[u][d][l][r][0] = 0;
dp[u][d][l][r][1] = max({
dp[u][d - 1][l][r][1] + len,
l > L ? dp[u][d][l - 1][r][1] : 0,
r < R ? dp[u][d][l][r + 1][1] : 0,
});
}else if(d == i){
dp[u][d][l][r][1] = 0;
dp[u][d][l][r][0] = max({
dp[u + 1][d][l][r][0] + len,
l > L ? dp[u][d][l - 1][r][0] : 0,
r < R ? dp[u][d][l][r + 1][0] : 0,
});
}else{
dp[u][d][l][r][0] = max({
dp[u + 1][d][l][r][0] + len,
dp[u + 1][d][l][r][1] + len,
l > L ? dp[u][d][l - 1][r][0] : 0,
r < R ? dp[u][d][l][r + 1][0] : 0,
});
dp[u][d][l][r][1] = max({
dp[u][d - 1][l][r][0] + len,
dp[u][d - 1][l][r][1] + len,
l > L ? dp[u][d][l - 1][r][1] : 0,
r < R ? dp[u][d][l][r + 1][1] : 0,
});
}
ans = max({
ans,
dp[u][d][l][r][0],
dp[u][d][l][r][1]
});
// cerr << u << ' ' << d << ' ' << l << ' ' << r << ' ' << dp[u][d][l][r][0] << ' ' << dp[u][d][l][r][1] << '\n';
}
// cerr << '\n';
}
// cerr << '\n';
}
}
// cerr << '\n';
// cerr << '\n';
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |