#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()
const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 2007;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int mat[MAXN][MAXN], n;
ii p[MAXN];
int prvi(){
int ans = inf;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(mat[i][j]){
ans = min(ans, i * j);
ans = min(ans, (n - i + 1) * j);
ans = min(ans, (n - i + 1) * (n - j + 1));
ans = min(ans, i * (n - j + 1));
}
}
}
return n * n - ans;
}
int leng(int id){
return p[id].Y - p[id].X + 1;
}
bool pod(int a, int b){
return p[b].X <= p[a].X and p[b].Y >= p[a].Y;
}
bool dobre(){
int opt = -1;
for(int i=1; i<=n; i++){
p[i] = {inf, -inf};
int j = 1;
while(j <= n and mat[i][j]) j++;
if(j > n) continue;
p[i].X = j;
j = n;
while(j and mat[i][j]) j--;
p[i].Y = j;
for(j = p[i].X; j<=p[i].Y; j++) if(mat[i][j]) return 0;
opt = i;
}
if(opt == -1) return 1;
for(int i=1; i<=n; i++) if(leng(i) > leng(opt)) opt = i;
for(int i=opt-1; i; i--) if(!pod(i, i + 1)) return 0;
for(int i=opt+1; i<=n; i++) if(!pod(i, i - 1)) return 0;
return 1;
}
int biggest_stadium(int _n, vector<vi> m){
int num = 0;
n = _n;
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
mat[i][j] = m[i - 1][j - 1];
num += mat[i][j];
}
if(dobre()) return n * n - num;
if(num == 1) return prvi();
if(n > 510) return 0;
}
Compilation message
soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:95:1: warning: control reaches end of non-void function [-Wreturn-type]
95 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
348 KB |
partial |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
0 ms |
348 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Correct |
1 ms |
348 KB |
ok |
| 7 |
Correct |
1 ms |
2648 KB |
ok |
| 8 |
Correct |
11 ms |
6488 KB |
ok |
| 9 |
Correct |
165 ms |
47408 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Partially correct |
0 ms |
344 KB |
partial |
| 4 |
Partially correct |
0 ms |
348 KB |
partial |
| 5 |
Incorrect |
0 ms |
348 KB |
wrong |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
348 KB |
partial |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Partially correct |
0 ms |
344 KB |
partial |
| 5 |
Partially correct |
0 ms |
348 KB |
partial |
| 6 |
Incorrect |
0 ms |
348 KB |
wrong |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
348 KB |
partial |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
0 ms |
348 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Partially correct |
0 ms |
344 KB |
partial |
| 7 |
Partially correct |
0 ms |
348 KB |
partial |
| 8 |
Incorrect |
0 ms |
348 KB |
wrong |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
348 KB |
partial |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
0 ms |
348 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Partially correct |
0 ms |
344 KB |
partial |
| 7 |
Partially correct |
0 ms |
348 KB |
partial |
| 8 |
Incorrect |
0 ms |
348 KB |
wrong |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
348 KB |
partial |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
0 ms |
348 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
348 KB |
ok |
| 7 |
Correct |
1 ms |
348 KB |
ok |
| 8 |
Correct |
1 ms |
2648 KB |
ok |
| 9 |
Correct |
11 ms |
6488 KB |
ok |
| 10 |
Correct |
165 ms |
47408 KB |
ok |
| 11 |
Partially correct |
0 ms |
344 KB |
partial |
| 12 |
Partially correct |
0 ms |
348 KB |
partial |
| 13 |
Incorrect |
0 ms |
348 KB |
wrong |
| 14 |
Halted |
0 ms |
0 KB |
- |
