#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
ll prefrow[2001][2001];
ll prefcol[2001][2001];
ll grid[2001][2001];
bool checkrow(ll a, ll b, ll row){
if (a>b) swap(a,b);
return (prefrow[row][b] - prefrow[row][a] + grid[row][a] == 0);
}
bool checkcol(ll a, ll b, ll col){
if (a>b) swap(a,b);
return (prefcol[b][col] - prefcol[a][col] + grid[a][col] == 0);
}
vector<array<ll,2>> possible;
ll ans = 0;
ll cnt =0 ;
void idkman(vector<array<ll,2>>& sus, ll n, ll point){
if (sus.size()==n){
ll temp = 0;
for (auto&i : sus) temp += i[1] - i[0]+1;
array<ll,2> firsts,lasts;
for (auto&i : sus){
if (i != array<ll,2>{0,-1}){
firsts = i;
break;
}
}
for (auto&i : sus){
if (i != array<ll,2>{0,-1}){
lasts = i;
}
}
if ((firsts[0] <= lasts[0] && lasts[1] <= firsts[1]) || (lasts[0]<=firsts[0]&&firsts[1]<=lasts[1])){
ans = max(ans, temp);
}
return;
}
cnt++;
for (auto&i : possible){
if (i != array<ll,2>{0,-1} && prefrow[sus.size()][i[1]]-prefrow[sus.size()][i[0]]+grid[sus.size()][i[0]] != 0) continue;
if (sus.size() && i != array<ll,2>{0,-1}){
ll left = sus[sus.size()-1][0];
ll right = sus[sus.size()-1][1];
if (!(left==0 && right==-1) && !(left<=i[0] && i[1] <= right) && sus.size()>point){
continue;
}
if (!(left==0 && right==-1) && !(i[0]<=left && right <= i[1]) && sus.size()<=point){
continue;
}
}
if (sus.size() && i == array<ll,2>{0,-1} && sus[sus.size()-1] != i){
ll temp = 0;
for (auto&i : sus) temp += i[1] - i[0]+1;
array<ll,2> firsts,lasts;
for (auto&i : sus){
if (i != array<ll,2>{0,-1}){
firsts = i;
break;
}
}
for (auto&i : sus){
if (i != array<ll,2>{0,-1}){
lasts = i;
}
}
if ((firsts[0] <= lasts[0] && lasts[1] <= firsts[1]) || (lasts[0]<=firsts[0]&&firsts[1]<=lasts[1])){
ans = max(ans, temp);
}
continue;
}
sus.push_back(i);
idkman(sus, n, point);
sus.pop_back();
}
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
possible.clear();
ans = 0;
FOR(i,0,N){
FOR(j,0,N){
grid[i][j] = F[i][j];
}
}
FOR(i,0,N){
prefrow[i][0] = F[i][0];
FOR(j,1,N){
prefrow[i][j] = prefrow[i][j-1] + F[i][j];
}
}
FOR(j,0,N){
prefcol[0][j] = F[0][j];
FOR(i,1,N){
prefcol[i][j] = prefcol[i-1][j] + F[i][j];
}
}
FOR(i,0,N){
FOR(j,i,N){
possible.push_back({i,j});
}
}
possible.push_back({0,-1});
vector<array<ll,2>> lmao;
FOR(i,0,N){
idkman(lmao, N, i);
lmao.clear();
}
// vector<vector<ll>> special;
// FOR(i,a,b){
// FOR(j,c,d){
// temp -= grid[i][j];
// vector<vector<ll>> sus = {{i-1,j}, {i+1,j}, {i,j-1}, {i,j+1}};
// if (grid[i][j] != 1){
// bool flag = 0;
// for (auto&k : sus){
// if (0<=k[0] && k[0]<N && 0<=k[1] && k[1]<N){
// if (grid[k[0]][k[1]]==1) flag = 1;
// }
// }
// if (flag==1 || i==0 || i==N-1 || j==0 || j==N-1) special.push_back({i,j});
// }
// }
// }
// bool flag = false;
// for (auto&X : special){
// for (auto&Y : special){
// ll i = X[0], j = X[1], k = Y[0], l= Y[1];
// if (grid[i][j]==1 || grid[k][l] == 1) continue;
// bool check1 = (checkrow(l, j, i) && checkcol(k, i, l));
// bool check2 = (checkrow(l, j, k) && checkcol(k, i, j));
// if (!check1 && !check2) flag = true;
// }
// }
// if (!flag) ans = max(ans, temp);
return ans;
}
Compilation message
soccer.cpp: In function 'void idkman(std::vector<std::array<long long int, 2> >&, ll, ll)':
soccer.cpp:41:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
41 | if (sus.size()==n){
| ~~~~~~~~~~^~~
soccer.cpp:74:88: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
74 | if (!(left==0 && right==-1) && !(left<=i[0] && i[1] <= right) && sus.size()>point){
| ~~~~~~~~~~^~~~~~
soccer.cpp:77:88: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
77 | if (!(left==0 && right==-1) && !(i[0]<=left && right <= i[1]) && sus.size()<=point){
| ~~~~~~~~~~^~~~~~~
soccer.cpp:99:66: warning: 'lasts' may be used uninitialized in this function [-Wmaybe-uninitialized]
99 | if ((firsts[0] <= lasts[0] && lasts[1] <= firsts[1]) || (lasts[0]<=firsts[0]&&firsts[1]<=lasts[1])){
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:99:40: warning: '*((void*)& lasts +8)' may be used uninitialized in this function [-Wmaybe-uninitialized]
99 | if ((firsts[0] <= lasts[0] && lasts[1] <= firsts[1]) || (lasts[0]<=firsts[0]&&firsts[1]<=lasts[1])){
| ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:99:40: warning: '*((void*)& firsts +8)' may be used uninitialized in this function [-Wmaybe-uninitialized]
soccer.cpp:99:66: warning: 'firsts' may be used uninitialized in this function [-Wmaybe-uninitialized]
99 | if ((firsts[0] <= lasts[0] && lasts[1] <= firsts[1]) || (lasts[0]<=firsts[0]&&firsts[1]<=lasts[1])){
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:62:36: warning: '*((void*)& firsts +8)' may be used uninitialized in this function [-Wmaybe-uninitialized]
62 | if ((firsts[0] <= lasts[0] && lasts[1] <= firsts[1]) || (lasts[0]<=firsts[0]&&firsts[1]<=lasts[1])){
| ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:62:62: warning: 'firsts' may be used uninitialized in this function [-Wmaybe-uninitialized]
62 | if ((firsts[0] <= lasts[0] && lasts[1] <= firsts[1]) || (lasts[0]<=firsts[0]&&firsts[1]<=lasts[1])){
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:62:62: warning: 'lasts' may be used uninitialized in this function [-Wmaybe-uninitialized]
soccer.cpp:62:36: warning: '*((void*)& lasts +8)' may be used uninitialized in this function [-Wmaybe-uninitialized]
62 | if ((firsts[0] <= lasts[0] && lasts[1] <= firsts[1]) || (lasts[0]<=firsts[0]&&firsts[1]<=lasts[1])){
| ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Execution timed out |
4594 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 |
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 |
600 KB |
ok |
| 8 |
Correct |
0 ms |
344 KB |
ok |
| 9 |
Correct |
0 ms |
348 KB |
ok |
| 10 |
Correct |
0 ms |
348 KB |
ok |
| 11 |
Correct |
0 ms |
348 KB |
ok |
| 12 |
Correct |
1 ms |
348 KB |
ok |
| 13 |
Correct |
0 ms |
348 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
ok |
| 2 |
Correct |
1 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 |
0 ms |
348 KB |
ok |
| 8 |
Correct |
1 ms |
600 KB |
ok |
| 9 |
Correct |
0 ms |
344 KB |
ok |
| 10 |
Correct |
0 ms |
348 KB |
ok |
| 11 |
Correct |
0 ms |
348 KB |
ok |
| 12 |
Correct |
0 ms |
348 KB |
ok |
| 13 |
Correct |
1 ms |
348 KB |
ok |
| 14 |
Correct |
0 ms |
348 KB |
ok |
| 15 |
Correct |
1149 ms |
504 KB |
ok |
| 16 |
Correct |
147 ms |
348 KB |
ok |
| 17 |
Correct |
6 ms |
348 KB |
ok |
| 18 |
Correct |
1 ms |
600 KB |
ok |
| 19 |
Correct |
0 ms |
348 KB |
ok |
| 20 |
Correct |
0 ms |
348 KB |
ok |
| 21 |
Correct |
1 ms |
348 KB |
ok |
| 22 |
Incorrect |
1 ms |
348 KB |
wrong |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
ok |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Execution timed out |
4594 ms |
348 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
ok |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Execution timed out |
4594 ms |
348 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
ok |
| 2 |
Correct |
1 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Execution timed out |
4594 ms |
348 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
