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;
int n, ans = 0;
vector<vector<bool> > t(3e3, vector<bool>(3e3, false));
vector<vector<vector<int> > > dp(3e3, vector<vector<int> >(3e3, vector<int>(4, -1e9)));
void u(int i, int l, int r, int x, int y, int val) {
int j = 2 * n * l + r;
int k = 2 * x + y;
dp[i][j][k] = val;
}
int q(int i, int l, int r, int x, int y) {
int j = 2 * n * l + r;
int k = 2 * x + y;
return dp[i][j][k];
}
void get_dp(int i, int l, int r, int x, int y) {
for (int j = l; j <= r; j++) if (t[i][j]) return;
int mx = 0, L1 = 1, Ln = n, R1 = 1, Rn = n;
(x ? Ln = l : L1 = l);
(y ? R1 = r : Rn = r);
for (int L = L1; L <= Ln; L++) {
for (int R = R1; R <= Rn; R++) {
if (R < l || r < L) continue;
mx = max(mx, q(i - 1, L, R, x, y));
}
}
for (int X = 0; X <= x; X++) {
for (int Y = 0; Y <= y; Y++) {
mx = max(mx, q(i - 1, l, r, X, Y));
}
}
mx += (r - l) + 1;
u(i, l, r, x, y, mx);
ans = max(ans, mx);
}
int biggest_stadium(int N, std::vector<std::vector<int> > F) {
n = N;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
t[i][j] = F[i - 1][j - 1];
}
}
for (int i = 1; i <= n; i++) {
for (int l = 1; l <= n; l++) {
for (int r = l; r <= n; r++) {
for (int x = 0; x < 2; x++) {
for (int y = 0; y < 2; y++) {
get_dp(i, l, r, x, y);
}
}
}
}
}
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... |