This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2010;
int a[maxn][maxn], bef[maxn][maxn], aft[maxn][maxn];
int dp[510][510][510], pref[maxn][maxn];
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
int cnt = 0;
int x1 = 0, y1 = 0;
for (int i = 0; i < N; i ++)
for (int j = 0; j < N; j ++)
{
cnt += F[i][j];
if (F[i][j] == 1)
x1 = i + 1, y1 = j + 1;
a[i + 1][j + 1] = F[i][j];
}
if (cnt == 1)
{
int ans = N * N - min(x1, N - x1 + 1) * min(y1, N - y1 + 1);
return ans;
}
for (int j = 1; j <= N; j ++)
{
for (int i = 1; i <= N; i ++)
pref[i][j] = pref[i - 1][j] + a[i][j];
}
for (int i = 1; i <= N; i ++)
{
for (int j = 1; j <= N; j ++)
{
if (a[i][j] == 1)
bef[i][j] = j;
else
bef[i][j] = bef[i][j - 1];
}
aft[i][N + 1] = N + 1;
for (int j = N; j > 0; j --)
{
if (a[i][j] == 1)
aft[i][j] = j;
else
aft[i][j] = aft[i][j + 1];
}
}
int ans = 0;
for (int col = 1; col <= N; col ++)
///int col = 5;
{
for (int len = 1; len <= N; len ++)
{
for (int i = 1; i <= N - len + 1; i ++)
{
int j = i + len - 1;
if (pref[j][col] - pref[i - 1][col] > 0)
continue;
if (col != 1 && pref[j][col - 1] - pref[i - 1][col - 1] == 0)
{
dp[col][i][j] = dp[col - 1][i][j];
continue;
}
int left_width = N, right_width = N;
for (int k = i; k <= j; k ++)
{
left_width = min(left_width, col - bef[k][col]);
right_width = min(right_width, aft[k][col] - col);
}
int base_area = (j - i + 1) * (left_width + right_width - 1);
dp[col][i][j] = base_area;
if (left_width != col)
{
vector < int > split;
split.push_back(i - 1);
for (int k = i; k <= j; k ++)
{
if (bef[k][col] == col - left_width)
split.push_back(k);
}
split.push_back(j + 1);
for (int d = 1; d < (int)(split.size()); d ++)
{
///cout << "check " << split[d - 1] + 1 << " " << split[d] - 1 << endl;
int rem_area = (split[d] - split[d - 1] - 1) * (left_width + right_width - 1);
dp[col][i][j] = max(dp[col][i][j], dp[col][split[d - 1] + 1][split[d] - 1] - rem_area + base_area);
}
}
if (right_width != N + 1 - col)
{
vector < int > split;
split.push_back(i - 1);
for (int k = i; k <= j; k ++)
{
if (aft[k][col] == col + right_width)
split.push_back(k);
}
split.push_back(j + 1);
for (int d = 1; d < (int)(split.size()); d ++)
{
int rem_area = (split[d] - split[d - 1] - 1) * (left_width + right_width - 1);
dp[col][i][j] = max(dp[col][i][j], dp[col][split[d - 1] + 1][split[d] - 1] - rem_area + base_area);
}
}
ans = max(ans, dp[col][i][j]);
///cout << i << " : " << j << " = " << dp[col][i][j] << endl;
}
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |