#include<bits/stdc++.h>
#include "soccer.h"
using namespace std;
#define ll long long
#define ff first
#define ss second
#define ln "\n"
// ll n;
vector<vector<bool>> stad;
vector<vector<ll>> reach;
ll csearch(ll i, vector<vector<int>> &F, ll n){
if (i==n){
reach.clear();
reach.resize(n, vector<ll>(n));
for (ll j=0; j<n; j++){
for (ll k=0; k<n; k++){
reach[j][k]=!stad[j][k];
if (j) reach[j][k]+=reach[j-1][k];
if (k) reach[j][k]+=reach[j][k-1];
if (j and k) reach[j][k]-=reach[j-1][k-1];
}
}
auto calc = [](ll x1, ll y1, ll x2, ll y2){
return reach[x2][y2]-(x1>0?reach[x1-1][y2]:0)-(y1>0?reach[x2][y1-1]:0)+(x1>0 and y1>0?reach[x1-1][y1-1]:0);
};
bool pos=1;
for (ll j=0; j<n and pos; j++){
for (ll k=0; k<n and pos; k++){
if (stad[j][k]){
if (F[j][k]) {pos=0; continue;}
for (ll x=0; x<n and pos; x++){
for (ll y=0; y<n and pos; y++){
if (stad[x][y]){
if (!((calc(min(x, j), y, max(x, j), y)==0 or calc(min(x, j), k, max(x, j), k)==0)
and (calc(x, min(y, k), x, max(y, k))==0 or calc(j, min(y, k), j, max(y, k))==0))){
// cout << calc(min(x, j), y, max(x, j), y) << " " << calc(min(x, j), k, max(x, j), k) << ln;
// cout << calc(x, min(y, k), x, max(y, k)) << " " << calc(j, min(y, k), j, max(y, k)) << ln;
// cout << j << " " << k << " - " << x << " " << y << ln;
pos=0;
}
}
}
}
}
}
}
// for (ll i=0; i<n; i++){
// for (ll j=0; j<n; j++){
// cout << stad[i][j] << " ";
// }
// cout << ln;
// }
// cout << pos << ln;
// cout << ln;
if (pos){
// cout << "H\n";
ll ans=0;
for (ll i=0; i<n; i++)
for (ll j=0; j<n; j++)
if (stad[i][j]) ans++;
return ans;
}else return 0;
}else{
ll res=0;
for (ll j=0; j<(1<<n); j++){
for (ll k=0; k<n; k++){
if (j&(1<<k)){
stad[i][k]=1;
}
}
res=max(res, csearch(i+1, F, n));
for (ll k=0; k<n; k++){
if (j&(1<<k)){
stad[i][k]=0;
}
}
}
return res;
}
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
stad.clear();
stad.resize(N, vector<bool>(N));
return csearch(0, F, N);
}
// int biggest_stadium_F(int N, std::vector<std::vector<int>> F)
// {
// n=N;
// vector<vector<ll>> gr(n+1, vector<ll>(n+1));
// vector<vector<pair<ll, ll>>> A(N+2, vector<pair<ll, ll>>(N+2, {0, n+1}));
// for (ll i=1; i<=n; i++){
// for (ll j=1; j<=n; j++){
// gr[i][j]=F[i-1][j-1];
// A[i][j].ff=A[i][j-1].ff;
// if (gr[i][j]){
// A[i][j].ff=j;
// }
// }
// }
// for (ll i=1; i<=n; i++){
// for (ll j=n; j>=1; j--){
// A[i][j].ss=A[i][j+1].ss;
// if (gr[i][j]){
// A[i][j].ss=j;
// }
// }
// }
// // for (ll i=1; i<=n; i++){
// // for (ll j=1; j<=n; j++){
// // cout << A[i][j].ff << "|" << A[i][j].ss << " ";
// // }
// // cout << ln;
// // }
// // cout << ln;
// ll res=0;
// for (ll i=1; i<=n; i++){
// for (ll j=1; j<=n; j++){
// // vector<ll> debug;
// ll l=A[i][j].ff, r=A[i][j].ss;
// ll ans=-(r-l-1);
// ll ch=i;
// while (ch>0 and l<j and r>j and l<r){
// ans+=r-l-1;
// ch--;
// l = max(l, A[ch][j].ff);
// r = min(r, A[ch][j].ss);
// }
// l=A[i][j].ff; r=A[i][j].ss;
// // debug.push_back(ch);
// ch = i;
// while (ch<=n and l<j and r>j and l<r){
// ans+=r-l-1;
// ch++;
// l = max(l, A[ch][j].ff);
// r = min(r, A[ch][j].ss);
// }
// // debug.push_back(ch);
// // cout << i << " " << j << " -> " << ans << ": ";
// // for (auto cch:debug){
// // cout << cch << " ";
// // }
// // cout << ln;
// if (res<ans){
// res=ans;
// }
// }
// }
// return res;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4549 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
ok |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Execution timed out |
4558 ms |
348 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
ok |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Correct |
1 ms |
348 KB |
ok |
| 4 |
Correct |
1 ms |
348 KB |
ok |
| 5 |
Correct |
1 ms |
348 KB |
ok |
| 6 |
Correct |
1 ms |
500 KB |
ok |
| 7 |
Correct |
1 ms |
348 KB |
ok |
| 8 |
Correct |
1 ms |
348 KB |
ok |
| 9 |
Correct |
1 ms |
348 KB |
ok |
| 10 |
Correct |
1 ms |
348 KB |
ok |
| 11 |
Correct |
1 ms |
344 KB |
ok |
| 12 |
Correct |
1 ms |
348 KB |
ok |
| 13 |
Correct |
1 ms |
348 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4549 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4549 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4549 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4549 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
