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<pair<int, int>>> segs;
map<tuple<int, int, int, int>, int> dp1;
int solve(int i1, int i2, int l, int r) {
if (dp1.find({i1, i2, l, r}) != dp1.end()) {
return dp1[{i1, i2, l, r}];
}
int v = 0;
if (i1-1 >= 0) {
for (auto [x, y] : segs[i1-1]) {
if (r < x || y < l) {
continue;
}
v = max(v, solve(i1-1, i2, max(l, x), min(r, y)));
}
}
if (i2+1 < n) {
for (auto [x, y] : segs[i2+1]) {
if (r < x || y < l) {
continue;
}
v = max(v, solve(i1, i2+1, max(l, x), min(r, y)));
}
}
dp1[{i1, i2, l, r}] = v+(r-l+1);
return v+(r-l+1);
}
int biggest_stadium(int N, vector<vector<int>> f) {
n = N;
segs.resize(n);
for (int i = 0; i < n; i++) {
int l = -1, r = -1;
for (int j = 0; j < n; j++) {
if (f[i][j] == 0) {
if (l == -1) {
l = j;
}
r = j;
} else {
if (l != -1) {
segs[i].push_back({l, r});
}
l = -1;
}
}
if (l != -1) {
segs[i].push_back({l, r});
}
}
for (int i = 0; i < n; i++) {
for (auto [x, y] : segs[i]) {
ans = max(ans, solve(i, i, 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... |