#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 hh[N][N][N][N], vv[N][N][N][N], hh2[N][N][N][N], vv2[N][N][N][N];
int biggest_stadium(int n, std::vector<std::vector<int>> a)
{
int nn = n;
n += n;
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;
}
}
}
}
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(U2[row][mx] == -1){
hh[row][l][r][mx] = 0;
continue;
}
int cur = row - U2[row][mx], tot = row - U2[row][mx];
for(int dif = 1; dif <= max(mx - l, r - mx); ++dif){
int x = mx - dif;
int y = mx + dif;
int sz = n + 1;
int o = 0;
if(x >= l)
sz = min(sz, row - U2[row][x]),++o;
if(y <= r)
sz = min(sz, row - U2[row][y]),++o;
if(sz >= cur){
tot += cur*o;
}else{
tot += sz*o;
cur = min(cur, sz);
}
}
hh[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 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){
hh2[row][l][r][mx] = 0;
continue;
}
int cur = D2[row][mx] - row, tot = D2[row][mx] - row;
for(int dif = 1; dif <= max(mx - l, r - mx); ++dif){
int x = mx - dif;
int y = mx + dif;
int sz = n + 1;
int o = 0;
if(x >= l)
sz = min(sz, D2[row][x] - row),++o;
if(y <= r)
sz = min(sz, D2[row][y] - row),++o;
if(sz >= cur){
tot += cur*o;
}else{
tot += sz*o;
cur = min(cur, sz);
}
}
hh2[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(L2[col][mx] == -1){
vv[col][l][r][mx] = 0;
continue;
}
int cur = col - L2[mx][col], tot = col - L2[mx][col];
for(int dif = 1; dif <= max(mx - l, r - mx); ++dif){
int x = mx - dif;
int y = mx + dif;
int sz = n + 1;
int o = 0;
if(x >= l)
sz = min(sz, col - L2[x][col]), ++o;
if(y <= r)
sz = min(sz, col - L2[y][col]), ++o;
if(sz >= cur){
tot += cur*o;
}else{
tot += o*sz;
cur = min(cur, sz);
}
}
vv[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 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){
vv2[col][l][r][mx] = 0;
continue;
}
int cur = R2[mx][col]-col, tot =R2[mx][col]-col;
for(int dif = 1; dif <= max(mx - l, r - mx); ++dif){
int x = mx - dif;
int y = mx + dif;
int sz = n + 1;
int o = 0;
if(x >= l)
sz = min(sz, R2[x][col]-col ), o++;
if(y <= r)
sz = min(sz, R2[y][col]-col), o++;
if(sz >= cur){
tot += cur * o;
}else{
tot += sz * o;
cur = min(cur, sz);
}
}
vv2[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 = 1;
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] + hh2[d][l][r][mx]);
x = max(x, hh[u][l][r][mx] + hh2[d][l][r][mx]);
x = max(x, hh[u][l][r][mx] + h2[d][l][r][mx]);
}
for(int mx = u; mx <= d; ++mx){
y = max(y, v[l][u][d][mx] + vv2[r][u][d][mx]);
y = max(y, vv[l][u][d][mx] + v2[r][u][d][mx]);
y = max(y, vv[l][u][d][mx] + vv2[r][u][d][mx]);
}
// if(sum + x + y > ans){
// cout << l << ' ' << r<< ' ' << u << ' ' << d <<' ' << sum + x + y << ' ' << sum << ' ' << x << ' ' << y << '\n';
// }
ans = max(ans, sum + x + y);
// cout << l << ' ' << r<< ' ' << u << ' ' << d <<' ' << sum + x + y << ' ' << sum << ' ' << x << ' ' << y << '\n';
}
}
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
31068 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
31064 KB |
ok |
| 2 |
Correct |
3 ms |
31068 KB |
ok |
| 3 |
Correct |
3 ms |
31068 KB |
ok |
| 4 |
Correct |
3 ms |
31068 KB |
ok |
| 5 |
Correct |
1 ms |
14684 KB |
ok |
| 6 |
Correct |
3 ms |
31064 KB |
ok |
| 7 |
Runtime error |
211 ms |
14932 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
31064 KB |
ok |
| 2 |
Correct |
3 ms |
31068 KB |
ok |
| 3 |
Correct |
3 ms |
31068 KB |
ok |
| 4 |
Correct |
3 ms |
31212 KB |
ok |
| 5 |
Correct |
3 ms |
31068 KB |
ok |
| 6 |
Correct |
2 ms |
31208 KB |
ok |
| 7 |
Correct |
3 ms |
31068 KB |
ok |
| 8 |
Correct |
3 ms |
31068 KB |
ok |
| 9 |
Correct |
3 ms |
31068 KB |
ok |
| 10 |
Correct |
3 ms |
31068 KB |
ok |
| 11 |
Correct |
3 ms |
31068 KB |
ok |
| 12 |
Correct |
3 ms |
31064 KB |
ok |
| 13 |
Correct |
2 ms |
31212 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
31068 KB |
ok |
| 2 |
Correct |
3 ms |
31064 KB |
ok |
| 3 |
Correct |
3 ms |
31068 KB |
ok |
| 4 |
Correct |
3 ms |
31068 KB |
ok |
| 5 |
Correct |
3 ms |
31212 KB |
ok |
| 6 |
Correct |
3 ms |
31068 KB |
ok |
| 7 |
Correct |
2 ms |
31208 KB |
ok |
| 8 |
Correct |
3 ms |
31068 KB |
ok |
| 9 |
Correct |
3 ms |
31068 KB |
ok |
| 10 |
Correct |
3 ms |
31068 KB |
ok |
| 11 |
Correct |
3 ms |
31068 KB |
ok |
| 12 |
Correct |
3 ms |
31068 KB |
ok |
| 13 |
Correct |
3 ms |
31064 KB |
ok |
| 14 |
Correct |
2 ms |
31212 KB |
ok |
| 15 |
Correct |
3 ms |
31064 KB |
ok |
| 16 |
Correct |
3 ms |
31208 KB |
ok |
| 17 |
Correct |
3 ms |
31068 KB |
ok |
| 18 |
Correct |
3 ms |
31068 KB |
ok |
| 19 |
Correct |
3 ms |
31064 KB |
ok |
| 20 |
Correct |
3 ms |
31064 KB |
ok |
| 21 |
Correct |
3 ms |
31200 KB |
ok |
| 22 |
Correct |
3 ms |
31064 KB |
ok |
| 23 |
Correct |
3 ms |
31068 KB |
ok |
| 24 |
Correct |
3 ms |
31068 KB |
ok |
| 25 |
Incorrect |
3 ms |
31068 KB |
wrong |
| 26 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
31068 KB |
ok |
| 2 |
Correct |
3 ms |
31064 KB |
ok |
| 3 |
Correct |
3 ms |
31068 KB |
ok |
| 4 |
Correct |
3 ms |
31068 KB |
ok |
| 5 |
Correct |
3 ms |
31068 KB |
ok |
| 6 |
Correct |
3 ms |
31068 KB |
ok |
| 7 |
Correct |
3 ms |
31212 KB |
ok |
| 8 |
Correct |
3 ms |
31068 KB |
ok |
| 9 |
Correct |
2 ms |
31208 KB |
ok |
| 10 |
Correct |
3 ms |
31068 KB |
ok |
| 11 |
Correct |
3 ms |
31068 KB |
ok |
| 12 |
Correct |
3 ms |
31068 KB |
ok |
| 13 |
Correct |
3 ms |
31068 KB |
ok |
| 14 |
Correct |
3 ms |
31068 KB |
ok |
| 15 |
Correct |
3 ms |
31064 KB |
ok |
| 16 |
Correct |
2 ms |
31212 KB |
ok |
| 17 |
Correct |
3 ms |
31064 KB |
ok |
| 18 |
Correct |
3 ms |
31208 KB |
ok |
| 19 |
Correct |
3 ms |
31068 KB |
ok |
| 20 |
Correct |
3 ms |
31068 KB |
ok |
| 21 |
Correct |
3 ms |
31064 KB |
ok |
| 22 |
Correct |
3 ms |
31064 KB |
ok |
| 23 |
Correct |
3 ms |
31200 KB |
ok |
| 24 |
Correct |
3 ms |
31064 KB |
ok |
| 25 |
Correct |
3 ms |
31068 KB |
ok |
| 26 |
Correct |
3 ms |
31068 KB |
ok |
| 27 |
Incorrect |
3 ms |
31068 KB |
wrong |
| 28 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
31068 KB |
ok |
| 2 |
Correct |
3 ms |
31064 KB |
ok |
| 3 |
Correct |
3 ms |
31068 KB |
ok |
| 4 |
Correct |
3 ms |
31068 KB |
ok |
| 5 |
Correct |
3 ms |
31068 KB |
ok |
| 6 |
Correct |
3 ms |
31068 KB |
ok |
| 7 |
Correct |
3 ms |
31212 KB |
ok |
| 8 |
Correct |
3 ms |
31068 KB |
ok |
| 9 |
Correct |
2 ms |
31208 KB |
ok |
| 10 |
Correct |
3 ms |
31068 KB |
ok |
| 11 |
Correct |
3 ms |
31068 KB |
ok |
| 12 |
Correct |
3 ms |
31068 KB |
ok |
| 13 |
Correct |
3 ms |
31068 KB |
ok |
| 14 |
Correct |
3 ms |
31068 KB |
ok |
| 15 |
Correct |
3 ms |
31064 KB |
ok |
| 16 |
Correct |
2 ms |
31212 KB |
ok |
| 17 |
Correct |
3 ms |
31064 KB |
ok |
| 18 |
Correct |
3 ms |
31208 KB |
ok |
| 19 |
Correct |
3 ms |
31068 KB |
ok |
| 20 |
Correct |
3 ms |
31068 KB |
ok |
| 21 |
Correct |
3 ms |
31064 KB |
ok |
| 22 |
Correct |
3 ms |
31064 KB |
ok |
| 23 |
Correct |
3 ms |
31200 KB |
ok |
| 24 |
Correct |
3 ms |
31064 KB |
ok |
| 25 |
Correct |
3 ms |
31068 KB |
ok |
| 26 |
Correct |
3 ms |
31068 KB |
ok |
| 27 |
Incorrect |
3 ms |
31068 KB |
wrong |
| 28 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
31068 KB |
ok |
| 2 |
Correct |
3 ms |
31064 KB |
ok |
| 3 |
Correct |
3 ms |
31068 KB |
ok |
| 4 |
Correct |
3 ms |
31068 KB |
ok |
| 5 |
Correct |
3 ms |
31068 KB |
ok |
| 6 |
Correct |
1 ms |
14684 KB |
ok |
| 7 |
Correct |
3 ms |
31064 KB |
ok |
| 8 |
Runtime error |
211 ms |
14932 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
