#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) });
}
int ans = 0, n = N;
int mat[N+1][N+1];
vector<vector<int> > ver(n+1, vector<int>(n+1));
vector<vector<int> > hor(n+1, vector<int>(n+1));
memset(mat, 0, sizeof(mat));
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());
auto queryHor = [&](int row, int i, int j) {
return hor[row][max(i, j)] - hor[row][min(i, j)-1];
};
auto queryVer = [&](int col, int i, int j) {
return ver[col][max(i, j)] - ver[col][min(i, j)-1];
};
int m = v.size();
if(N <= 3) {
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 x = max(v[j].second, v[i].second), y = min(v[j].second, v[i].second);
int p = hor[v[i].first][x] - hor[v[i].first][y-1];
if(p) {
ok1 = 0;
ok2 = 0;
ok = 0;
break;
}
}
if(v[i].second == v[j].second) {
int x = max(v[j].first, v[i].first), y = min(v[j].first, v[i].first);
int p = ver[v[i].second][x] - ver[v[i].second][y-1];
if(p) {
ok1 = 0;
ok2 = 0;
ok = 0;
break;
}
}
if(v[i].first != v[j].first && v[i].second != v[j].second) {
pair<int, int> a = v[i];
pair<int, int> b = v[j];
if(a.first > b.first) swap(a, b);
//right-UD
if(queryHor(a.first, a.second, b.second) || queryVer(b.second, a.first, b.first)) ok1 = 0;
//UP-right
if(queryVer(a.second, a.first, b.first) || queryHor(b.first, a.second, b.second)) ok2 = 0;
}
if(!ok1 && !ok2) {
ok = 0;
break;
}
}
}
if(ok) ans = max(ans, __builtin_popcount(s));
}
return ans;
}
//check full
bool ok = 1;
for(int i=0; i<n; i++) {
for(int j=i+1; j<n; j++) {
if(v[i].first == v[j].first) {
int x = min(v[i].second, v[i].second), y = max(v[i].second, v[i].second);
if(hor[v[i].first][y] - hor[v[i].first][x-1]) {
ok = 0;
break;
}
}
if(v[i].second == v[j].second) {
int x = min(v[i].first, v[j].first), y = max(v[i].first, v[j].first);
if(ver[v[i].second][y] - ver[v[i].second][x-1]) {
ok = 0;
break;
}
}
if(v[i].first != v[j].first && v[i].second != v[j].second) {
pair<int, int> a = v[i];
pair<int, int> b = v[j];
if(a.first > b.first) swap(a, b);
int ok1 = queryHor(a.first, a.second, b.second) + queryVer(b.second, a.first, b.first);
int ok2 = queryVer(a.second, a.first, b.first) + queryHor(b.first, a.second, b.second);
if(ok1 && ok2) {
ok = 0;
break;
}
}
}
}
return (ok ? m : m+1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 ms |
348 KB |
ok |
| 6 |
Correct |
1 ms |
344 KB |
ok |
| 7 |
Correct |
1 ms |
344 KB |
ok |
| 8 |
Correct |
16 ms |
2692 KB |
ok |
| 9 |
Correct |
245 ms |
35840 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
1 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 |
0 ms |
348 KB |
ok |
| 8 |
Correct |
0 ms |
348 KB |
ok |
| 9 |
Correct |
0 ms |
348 KB |
ok |
| 10 |
Correct |
0 ms |
436 KB |
ok |
| 11 |
Correct |
0 ms |
348 KB |
ok |
| 12 |
Correct |
0 ms |
348 KB |
ok |
| 13 |
Correct |
0 ms |
348 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
