#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long
#define ff first
#define ss second
const int N = 32;
int arr[4][2]={
{0, 1},
{0, -1},
{1, 0},
{-1, 0}
};
int h[N][N][N][N], v[N][N][N][N], h2[N][N][N][N], v2[N][N][N][N];
int biggest_stadium(int n, std::vector<std::vector<int>> a)
{
int nn = n;
n += 3;
vector<vector<int>> U(n, vector<int>(n));
vector<vector<int>> U2(n, vector<int>(n));
vector<vector<int>> L(n, vector<int>(n));
vector<vector<int>> L2(n, vector<int>(n));
vector<vector<int>> R2(n, vector<int>(n));
vector<vector<int>> D2(n, vector<int>(n));
vector<vector<int>> pref(n, vector<int>(n));
n =nn;
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
pref[i][j] = a[i][j] == 0;
if(i > 0) pref[i][j] += pref[i - 1][j];
if(j > 0) pref[i][j] += pref[i][j - 1];
if(i > 0 && j > 0) pref[i][j] -= pref[i - 1][j - 1];
if(i == 0){
if(a[i][j] == 1) U[i][j] = i;
else U[i][j] = -1;
}else{
if(a[i][j] == 1){
if(a[i - 1][j] == 1) U[i][j] = U[i - 1][j];
else U[i][j] = i;
}else{
U[i][j] = -1;
}
}
if(j == 0){
if(a[i][j] == 1) L[i][j] = j;
else L[i][j] = -1;
}else{
if(a[i][j] == 1){
if(a[i][j - 1] == 1) L[i][j] = L[i][j - 1];
else L[i][j] = j;
}else{
L[i][j] = -1;
}
}
if(i == 0){
if(a[i][j] == 0) U2[i][j] = i;
else U2[i][j] = -1;
}else{
if(a[i][j] == 0){
if(a[i - 1][j] == 0) U2[i][j] = U2[i - 1][j];
else U2[i][j] = i;
}else{
U2[i][j] = -1;
}
}
if(j == 0){
if(a[i][j] == 0) L2[i][j] = j;
else L2[i][j] = -1;
}else{
if(a[i][j] == 0){
if(a[i][j - 1] == 0) L2[i][j] = L2[i][j - 1];
else L2[i][j] = j;
}else{
L2[i][j] = -1;
}
}
}
for(int j = n-1; j >= 0; --j){
if(j == n-1){
if(a[i][j] == 0) R2[i][j] = j;
else R2[i][j] = -1;
}else{
if(a[i][j] == 0){
if(a[i][j + 1] == 0) R2[i][j] = R2[i][j + 1];
else R2[i][j] = j;
}else{
R2[i][j] = -1;
}
}
}
}
for(int i = n-1; i >= 0; --i){
for(int j = 0; j < n; ++j){
if(i == n-1){
if(a[i][j] == 0) D2[i][j] = i;
else D2[i][j] = -1;
}else{
if(a[i][j] == 0){
if(a[i + 1][j] == 0) D2[i][j] = D2[i + 1][j];
else D2[i][j] = i;
}else{
D2[i][j] = -1;
}
}
}
}
queue<pair<int, int>> q;
vector<vector<bool>> vis(n, vector<bool>(n));
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if(a[i][j] == 0){
q.push({i, j});
vis[i][j] = 1;
break;
}
}
if(q.size()) break;
}
int sz = 0;
while(!q.empty()){
int x = q.front().ff;
int y = q.front().ss;
q.pop();
for(int i = 0; i < 4; ++i){
int nx = x + arr[i][0];
int ny = y + arr[i][1];
if(nx >= 0 && ny >= 0 && nx < n && ny < n && !vis[nx][ny] && a[nx][ny] == 0){
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
for(int row = 0; row < n; ++row){
for(int l = 0; l < n; ++l){
for(int r = l; r < n; ++r){
for(int mx = l; mx <= r; ++mx){
if(U2[row][mx] == -1){
h[row][l][r][mx] = 0;
continue;
}
int cur = row - U2[row][mx], tot = row - U2[row][mx];
for(int i = mx - 1; i >= l; --i){
int szz = row - U2[row][i];
if(szz >= cur){
tot += cur;
}else{
tot += szz;
cur = min(cur, szz);
}
}
cur = row - U2[row][mx];
for(int i = mx + 1; i <= r; ++i){
int szz = row - U2[row][i];
if(szz >= cur){
tot += cur;
}else{
tot += szz;
cur = min(cur, szz);
}
}
h[row][l][r][mx] = tot;
}
}
}
}
for(int row = 0; row < n; ++row){
for(int l = 0; l < n; ++l){
for(int r = l; r < n; ++r){
for(int mx = l; mx <= r; ++mx){
if(D2[row][mx] == -1){
h2[row][l][r][mx] = 0;
continue;
}
int cur = D2[row][mx] - row, tot = D2[row][mx] - row;
for(int i = mx - 1; i >= l; --i){
int szz = D2[row][i] - row;
if(szz >= cur){
tot += cur;
}else{
tot += szz;
cur = min(cur, szz);
}
}
cur = D2[row][mx] - row;
for(int i = mx + 1; i <= r; ++i){
int szz = D2[row][i] - row;
if(szz >= cur){
tot += cur;
}else{
tot += szz;
cur = min(cur, szz);
}
}
h2[row][l][r][mx] = tot;
}
}
}
}
for(int col = 0; col < n; ++col){
for(int l = 0; l < n; ++l){
for(int r = l; r < n; ++r){
for(int mx = l; mx <= r; ++mx){
if(L2[col][mx] == -1){
v[col][l][r][mx] = 0;
continue;
}
int cur = col - L2[mx][col] , tot = col - L2[mx][col];
for(int i = mx - 1; i >= l; --i){
int szz = col - L2[i][col] ;
if(szz >= cur){
tot += cur;
}else{
tot += szz;
cur = min(cur, szz);
}
}
cur = col - L2[mx][col] ;
for(int i = mx + 1; i <= r; ++i){
int szz = col - L2[i][col];
if(szz >= cur){
tot += cur;
}else{
tot += szz;
cur = min(cur, szz);
}
}
v[col][l][r][mx] = tot;
}
}
}
}
for(int col = 0; col < n; ++col){
for(int l = 0; l < n; ++l){
for(int r = l; r < n; ++r){
for(int mx = l; mx <= r; ++mx){
if(R2[col][mx] == -1){
v2[col][l][r][mx] = 0;
continue;
}
int cur = R2[mx][col] - col , tot = R2[mx][col] - col;
for(int i = mx - 1; i >= l; --i){
int szz = R2[i][col] - col;
if(szz >= cur){
tot += cur;
}else{
tot += szz;
cur = min(cur, szz);
}
}
cur = R2[mx][col] - col;
for(int i = mx + 1; i <= r; ++i){
int szz = R2[i][col] - col;
if(szz >= cur){
tot += cur;
}else{
tot += szz;
cur = min(cur, szz);
}
}
v2[col][l][r][mx] = tot;
}
}
}
}
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < n; ++j){
// cout << pref[i][j] << ' ';
// }
// cout << '\n';
// }
int ans = 0;
for(int l = 0; l < n; ++l){
for(int r = l; r < n; ++r){
for(int u = 0; u < n; ++u){
for(int d = u; d < n; ++d){
int sum = pref[d][r];
if(u > 0) sum -= pref[u - 1][r];
if(l > 0) sum -= pref[d][l - 1];
if(u > 0 && l > 0) sum += pref[u - 1][l - 1];
if(sum != (r - l + 1) * (d - u + 1)) continue;
// cout << l << ' ' << r << ' ' << u << ' ' << d << ' ' << (r - l + 1) * (d - u + 1) << '\n';
int x = 0, y = 0;
for(int mx = l; mx <= r; ++mx){
x = max(x, h[u][l][r][mx] + h2[d][l][r][mx]);
}
for(int mx = u; mx <= d; ++mx){
y = max(y, v[l][u][d][mx] + v2[r][u][d][mx]);
}
ans = max(ans, sum + x + y);
}
}
}
}
return ans;
}
Compilation message
soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:124:7: warning: unused variable 'sz' [-Wunused-variable]
124 | int sz = 0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
14684 KB |
ok |
| 2 |
Correct |
2 ms |
14684 KB |
ok |
| 3 |
Correct |
1 ms |
14684 KB |
ok |
| 4 |
Correct |
2 ms |
14684 KB |
ok |
| 5 |
Correct |
1 ms |
6492 KB |
ok |
| 6 |
Correct |
2 ms |
14684 KB |
ok |
| 7 |
Runtime error |
207 ms |
13500 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
14684 KB |
ok |
| 2 |
Correct |
2 ms |
14684 KB |
ok |
| 3 |
Correct |
2 ms |
14684 KB |
ok |
| 4 |
Correct |
1 ms |
14684 KB |
ok |
| 5 |
Correct |
1 ms |
14684 KB |
ok |
| 6 |
Correct |
2 ms |
14680 KB |
ok |
| 7 |
Incorrect |
1 ms |
14684 KB |
wrong |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
ok |
| 2 |
Correct |
1 ms |
14684 KB |
ok |
| 3 |
Correct |
2 ms |
14684 KB |
ok |
| 4 |
Correct |
2 ms |
14684 KB |
ok |
| 5 |
Correct |
1 ms |
14684 KB |
ok |
| 6 |
Correct |
1 ms |
14684 KB |
ok |
| 7 |
Correct |
2 ms |
14680 KB |
ok |
| 8 |
Incorrect |
1 ms |
14684 KB |
wrong |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
ok |
| 2 |
Correct |
1 ms |
14684 KB |
ok |
| 3 |
Correct |
2 ms |
14684 KB |
ok |
| 4 |
Correct |
1 ms |
14684 KB |
ok |
| 5 |
Correct |
2 ms |
14684 KB |
ok |
| 6 |
Correct |
2 ms |
14684 KB |
ok |
| 7 |
Correct |
1 ms |
14684 KB |
ok |
| 8 |
Correct |
1 ms |
14684 KB |
ok |
| 9 |
Correct |
2 ms |
14680 KB |
ok |
| 10 |
Incorrect |
1 ms |
14684 KB |
wrong |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
ok |
| 2 |
Correct |
1 ms |
14684 KB |
ok |
| 3 |
Correct |
2 ms |
14684 KB |
ok |
| 4 |
Correct |
1 ms |
14684 KB |
ok |
| 5 |
Correct |
2 ms |
14684 KB |
ok |
| 6 |
Correct |
2 ms |
14684 KB |
ok |
| 7 |
Correct |
1 ms |
14684 KB |
ok |
| 8 |
Correct |
1 ms |
14684 KB |
ok |
| 9 |
Correct |
2 ms |
14680 KB |
ok |
| 10 |
Incorrect |
1 ms |
14684 KB |
wrong |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
ok |
| 2 |
Correct |
1 ms |
14684 KB |
ok |
| 3 |
Correct |
2 ms |
14684 KB |
ok |
| 4 |
Correct |
1 ms |
14684 KB |
ok |
| 5 |
Correct |
2 ms |
14684 KB |
ok |
| 6 |
Correct |
1 ms |
6492 KB |
ok |
| 7 |
Correct |
2 ms |
14684 KB |
ok |
| 8 |
Runtime error |
207 ms |
13500 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
