#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
int cnt = 0;
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) cnt += (F[i][j] == 1);
if(!cnt) return N * N;
if(cnt == 1) {
int x=0, y=0;
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
if(F[i][j] == 1) x = i, y = j;
return N * N - min({ (x + 1) * (y + 1), (N - x) * (y + 1), (x + 1) * (N - y), (N - x) * (N - y) });
}
if(N <= 3) {
int ans = 0, n = N;
int mat[N+1][N+1], hor[N+1][N+1], ver[N+1][N+1];
memset(mat, 0, sizeof(mat));
memset(hor, 0, sizeof(hor));
memset(ver, 0, sizeof(ver));
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++) mat[i][j] = F[i-1][j-1];
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) hor[i][j] = hor[i][j-1] + mat[i][j];
for(int j=1; j<=n; j++)
for(int i=1; i<=n; i++) ver[j][i] = ver[j][i-1] + mat[i][j];
vector<pair<int, int> > v;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) if(!mat[i][j]) v.push_back({ i, j });
sort(v.begin(), v.end());
int m = v.size();
for(int s=0; s<(1<<m); s++) {
if(__builtin_popcount(s) <= ans) continue;
bool ok = 1;
for(int i=0; i<m; i++) {
if((s & (1 << i)) == 0) continue;
for(int j=i+1; j<m; j++) {
if((s & (1 << j)) == 0) continue;
bool ok1=1, ok2=1;
if(v[i].first == v[j].first) {
int p = hor[v[i].first][v[j].second] - hor[v[i].first][v[i].second-1];
if(p) {
ok1 = 0;
ok2 = 0;
ok = 0;
break;
}
}
if(v[i].second == v[j].second) {
int p = ver[v[i].second][v[j].first] - ver[v[i].second][v[i].second-1];
if(p) {
ok1 = 0;
ok2 = 0;
ok = 0;
break;
}
}
if(v[i].first != v[j].first && v[i].second != v[j].second) {
int a = min(v[i].first, v[j].first);
int b = max(v[i].first, v[j].first);
int c = min(v[i].second, v[j].second);
int d = max(v[i].second, v[j].second);
int p1 = hor[b][d] - hor[b][c-1];
int p2 = ver[d][b] - ver[d][a-1];
int p3 = ver[c][b] - ver[c][a-1];
int p4 = hor[a][d] - hor[a][c-1];
if(p1 || p2) ok1 = 0;
if(p3 || p4) ok2 = 0;
}
if(!ok1 && !ok2) {
ok = 0;
break;
}
}
}
if(ok) ans = max(ans, __builtin_popcount(s));
}
return ans;
}
}
Compilation message
soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:103:1: warning: control reaches end of non-void function [-Wreturn-type]
103 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
27 ms |
348 KB |
partial |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
1 ms |
348 KB |
ok |
| 5 |
Correct |
0 ms |
436 KB |
ok |
| 6 |
Correct |
0 ms |
348 KB |
ok |
| 7 |
Correct |
1 ms |
348 KB |
ok |
| 8 |
Correct |
15 ms |
2908 KB |
ok |
| 9 |
Correct |
239 ms |
39576 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
344 KB |
ok |
| 4 |
Correct |
0 ms |
344 KB |
ok |
| 5 |
Partially correct |
1 ms |
348 KB |
partial |
| 6 |
Correct |
1 ms |
344 KB |
ok |
| 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 |
27 ms |
348 KB |
partial |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
0 ms |
344 KB |
ok |
| 5 |
Correct |
0 ms |
344 KB |
ok |
| 6 |
Partially correct |
1 ms |
348 KB |
partial |
| 7 |
Correct |
1 ms |
344 KB |
ok |
| 8 |
Partially correct |
0 ms |
348 KB |
partial |
| 9 |
Incorrect |
0 ms |
348 KB |
wrong |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
27 ms |
348 KB |
partial |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
0 ms |
348 KB |
ok |
| 5 |
Correct |
1 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
344 KB |
ok |
| 7 |
Correct |
0 ms |
344 KB |
ok |
| 8 |
Partially correct |
1 ms |
348 KB |
partial |
| 9 |
Correct |
1 ms |
344 KB |
ok |
| 10 |
Partially correct |
0 ms |
348 KB |
partial |
| 11 |
Incorrect |
0 ms |
348 KB |
wrong |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
27 ms |
348 KB |
partial |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
0 ms |
348 KB |
ok |
| 5 |
Correct |
1 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
344 KB |
ok |
| 7 |
Correct |
0 ms |
344 KB |
ok |
| 8 |
Partially correct |
1 ms |
348 KB |
partial |
| 9 |
Correct |
1 ms |
344 KB |
ok |
| 10 |
Partially correct |
0 ms |
348 KB |
partial |
| 11 |
Incorrect |
0 ms |
348 KB |
wrong |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
27 ms |
348 KB |
partial |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
0 ms |
348 KB |
ok |
| 5 |
Correct |
1 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
436 KB |
ok |
| 7 |
Correct |
0 ms |
348 KB |
ok |
| 8 |
Correct |
1 ms |
348 KB |
ok |
| 9 |
Correct |
15 ms |
2908 KB |
ok |
| 10 |
Correct |
239 ms |
39576 KB |
ok |
| 11 |
Correct |
0 ms |
344 KB |
ok |
| 12 |
Correct |
0 ms |
344 KB |
ok |
| 13 |
Partially correct |
1 ms |
348 KB |
partial |
| 14 |
Correct |
1 ms |
344 KB |
ok |
| 15 |
Partially correct |
0 ms |
348 KB |
partial |
| 16 |
Incorrect |
0 ms |
348 KB |
wrong |
| 17 |
Halted |
0 ms |
0 KB |
- |
