// incorrect/BM_wd_quadratic.cpp
#include "soccer.h"
#include <iostream>
const int MAXN = 3202;
int F[MAXN][MAXN];
int left[MAXN][MAXN];
int right[MAXN][MAXN];
int mid[MAXN][MAXN];
int last[MAXN];
int left2[MAXN][MAXN];
int right2[MAXN][MAXN];
int mid2[MAXN][MAXN];
int last2[MAXN];
int ans = 0;
int biggest_stadium(int N, std::vector<std::vector<int>> FF)
{
std::ios_base::sync_with_stdio(false);
std::cout.tie(0);
F[0][0] = 1;
F[0][N + 1] = 1;
F[N + 1][0] = 1;
F[N + 1][N + 1] = 1;
for (int i = 1; i <= N; i++)
{
F[0][i] = 1;
F[N + 1][i] = 1;
F[i][0] = 1;
F[i][N + 1] = 1;
for (int j = 1; j <= N; j++)
F[i][j] = FF[i - 1][j - 1];
}
for (int i = 1; i <= N; i++)
{
int start = 1;
for (int j = 1; j <= N + 1; j++)
{
if (F[i][j] == 1)
{
if (start < j)
{
int myLast = 0;
for (int k = start; k < j; k++)
myLast = std::max(myLast, last[k]);
int start2 = start, maxi = 0;
for (int k = start; k < j; k++)
{
if (F[myLast][k] == 1)
{
if (start2 < k)
{
if (start2 == start)
{
maxi = right[myLast][start2];
}
else
{
maxi = std::max(maxi, mid[myLast][k]);
}
}
start2 = k + 1;
}
}
if (start2 < j)
maxi = std::max(maxi, left[myLast][j - 1]);
mid[i][j] = maxi + (j - start) * (i - myLast);
}
start = j + 1;
}
}
start = 1;
int myLast = 0;
for (int j = 1; j <= N + 1; j++)
{
if (F[i][j] == 1)
{
start = j + 1;
myLast = 0;
}
else
{
left[i][j] = left[i][j - 1] - (j - start) * (i - myLast);
if (myLast >= last[j])
{
if (myLast == last[j])
{
left[i][j] = std::max(left[i][j], mid[myLast][j]);
}
else
{
left[i][j] = std::max(left[i][j], left[myLast][j]);
}
}
else
{
myLast = last[j];
left[i][j] = right[myLast][start];
}
left[i][j] += (j - start + 1) * (i - myLast);
}
}
start = N;
myLast = 0;
for (int j = N; j >= 0; j--)
{
if (F[i][j] == 1)
{
start = j - 1;
myLast = 0;
}
else
{
right[i][j] = right[i][j + 1] - (start - j) * (i - myLast);
if (myLast >= last[j])
{
if (myLast == last[j])
{
right[i][j] = std::max(right[i][j], mid[myLast][start + 1]);
}
else
{
right[i][j] = std::max(right[i][j], right[myLast][j]);
}
}
else
{
myLast = last[j];
right[i][j] = left[myLast][start];
}
right[i][j] += (start - j + 1) * (i - myLast);
}
}
for (int j = 0; j <= N + 1; j++)
if (F[i][j] == 1)
last[j] = i;
}
for (int j = 0; j <= N + 1; j++)
last2[j] = N + 1;
for (int i = N; i >= 1; i--)
{
int start = 1;
for (int j = 1; j <= N + 1; j++)
{
if (F[i][j] == 1)
{
if (start < j)
{
int myLast = N + 1;
for (int k = start; k < j; k++)
myLast = std::min(myLast, last2[k]);
int start2 = start, maxi = 0;
for (int k = start; k < j; k++)
{
if (F[myLast][k] == 1)
{
if (start2 < k)
{
if (start2 == start)
{
maxi = right2[myLast][start2];
}
else
{
maxi = std::max(maxi, mid2[myLast][k]);
}
}
start2 = k + 1;
}
}
if (start2 < j)
maxi = std::max(maxi, left2[myLast][j - 1]);
mid2[i][j] = maxi + (j - start) * (myLast - i);
ans = std::max(ans, mid[i][j] + mid2[i][j] - (j - start));
}
start = j + 1;
}
}
start = 1;
int myLast = N + 1;
for (int j = 1; j <= N + 1; j++)
{
if (F[i][j] == 1)
{
start = j + 1;
myLast = N + 1;
}
else
{
left2[i][j] = left2[i][j - 1] - (j - start) * (myLast - i);
if (myLast <= last2[j])
{
if (myLast == last2[j])
{
left2[i][j] = std::max(left2[i][j], mid2[myLast][j]);
}
else
{
left2[i][j] = std::max(left2[i][j], left2[myLast][j]);
}
}
else
{
myLast = last2[j];
left2[i][j] = right2[myLast][start];
}
left2[i][j] += (j - start + 1) * (myLast - i);
}
}
start = N;
myLast = N + 1;
for (int j = N; j >= 0; j--)
{
if (F[i][j] == 1)
{
start = j - 1;
myLast = N + 1;
}
else
{
right2[i][j] = right2[i][j + 1] - (start - j) * (myLast - i);
if (myLast <= last2[j])
{
if (myLast == last2[j])
{
right2[i][j] = std::max(right2[i][j], mid2[myLast][start + 1]);
}
else
{
right2[i][j] = std::max(right2[i][j], right2[myLast][j]);
}
}
else
{
myLast = last2[j];
right2[i][j] = left2[myLast][start];
}
right2[i][j] += (start - j + 1) * (myLast - i);
}
}
for (int j = 0; j <= N + 1; j++)
if (F[i][j] == 1)
last2[j] = i;
}
/*if(N<=50){
std::cerr << ans << '\n';
for(int i=0; i<=N+1; i++){
for(int j=0; j<=N+1; j++){
std::cerr << F[i][j] << '\t';
}
std::cerr << '\n';
}
std::cerr << '\n';
std::cerr << '\n';
for(int i=0; i<=N+1; i++){
for(int j=0; j<=N+1; j++){
std::cerr << mid[i][j] << '\t';
}
std::cerr << '\n';
}
std::cerr << '\n';
for(int i=0; i<=N+1; i++){
for(int j=0; j<=N+1; j++){
std::cerr << left[i][j] << '\t';
}
std::cerr << '\n';
}
std::cerr << '\n';
for(int i=0; i<=N+1; i++){
for(int j=0; j<=N+1; j++){
std::cerr << right[i][j] << '\t';
}
std::cerr << '\n';
}
std::cerr << '\n';
std::cerr << '\n';
for(int i=0; i<=N+1; i++){
for(int j=0; j<=N+1; j++){
std::cerr << mid2[i][j] << '\t';
}
std::cerr << '\n';
}
std::cerr << '\n';
for(int i=0; i<=N+1; i++){
for(int j=0; j<=N+1; j++){
std::cerr << left2[i][j] << '\t';
}
std::cerr << '\n';
}
std::cerr << '\n';
for(int i=0; i<=N+1; i++){
for(int j=0; j<=N+1; j++){
std::cerr << right2[i][j] << '\t';
}
std::cerr << '\n';
}
}*/
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
480 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
ok |
| 2 |
Correct |
1 ms |
440 KB |
ok |
| 3 |
Correct |
1 ms |
568 KB |
ok |
| 4 |
Correct |
0 ms |
596 KB |
ok |
| 5 |
Correct |
1 ms |
340 KB |
ok |
| 6 |
Correct |
1 ms |
340 KB |
ok |
| 7 |
Correct |
4 ms |
3412 KB |
ok |
| 8 |
Correct |
30 ms |
21584 KB |
ok |
| 9 |
Correct |
468 ms |
170832 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
ok |
| 2 |
Correct |
1 ms |
440 KB |
ok |
| 3 |
Correct |
1 ms |
340 KB |
ok |
| 4 |
Correct |
0 ms |
340 KB |
ok |
| 5 |
Incorrect |
1 ms |
340 KB |
wrong |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
480 KB |
ok |
| 2 |
Correct |
1 ms |
340 KB |
ok |
| 3 |
Correct |
1 ms |
440 KB |
ok |
| 4 |
Correct |
1 ms |
340 KB |
ok |
| 5 |
Correct |
0 ms |
340 KB |
ok |
| 6 |
Incorrect |
1 ms |
340 KB |
wrong |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
480 KB |
ok |
| 2 |
Correct |
1 ms |
340 KB |
ok |
| 3 |
Correct |
1 ms |
440 KB |
ok |
| 4 |
Correct |
1 ms |
568 KB |
ok |
| 5 |
Correct |
0 ms |
596 KB |
ok |
| 6 |
Correct |
1 ms |
340 KB |
ok |
| 7 |
Correct |
0 ms |
340 KB |
ok |
| 8 |
Incorrect |
1 ms |
340 KB |
wrong |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
480 KB |
ok |
| 2 |
Correct |
1 ms |
340 KB |
ok |
| 3 |
Correct |
1 ms |
440 KB |
ok |
| 4 |
Correct |
1 ms |
568 KB |
ok |
| 5 |
Correct |
0 ms |
596 KB |
ok |
| 6 |
Correct |
1 ms |
340 KB |
ok |
| 7 |
Correct |
0 ms |
340 KB |
ok |
| 8 |
Incorrect |
1 ms |
340 KB |
wrong |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
480 KB |
ok |
| 2 |
Correct |
1 ms |
340 KB |
ok |
| 3 |
Correct |
1 ms |
440 KB |
ok |
| 4 |
Correct |
1 ms |
568 KB |
ok |
| 5 |
Correct |
0 ms |
596 KB |
ok |
| 6 |
Correct |
1 ms |
340 KB |
ok |
| 7 |
Correct |
1 ms |
340 KB |
ok |
| 8 |
Correct |
4 ms |
3412 KB |
ok |
| 9 |
Correct |
30 ms |
21584 KB |
ok |
| 10 |
Correct |
468 ms |
170832 KB |
ok |
| 11 |
Correct |
1 ms |
340 KB |
ok |
| 12 |
Correct |
0 ms |
340 KB |
ok |
| 13 |
Incorrect |
1 ms |
340 KB |
wrong |
| 14 |
Halted |
0 ms |
0 KB |
- |
