| # | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1026535 | overwatch9 | Building 4 (JOI20_building4) | C++17 | 2610 ms | 524292 KiB |
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 <bits/stdc++.h>
using namespace std;
int n;
vector <int> a, b;
// let dp[i][j][2] say if its possible to have an answer if
// if we consider first i positions, j of them come from plan A
// and the last position is from plan A (0) or plan B (1)
const int maxn = 4001;
array <int, 3> goes_to[maxn][maxn][2];
bool dp[maxn][maxn][2];
bool ready[maxn][maxn][2];
bool solve(int i, int j, bool lst) {
if (i > n) {
return j == n/2;
}
if (ready[i][j][lst])
return dp[i][j][lst];
int ans = false;
// choose plan a now
if (j+1 <= n/2) {
if (lst == 0 && a[i-1] <= a[i]) {
bool res = solve(i+1, j+1, 0);
if (res) {
ans = res;
goes_to[i][j][lst] = {i+1, j+1, 0};
}
}
if (lst == 1 && b[i-1] <= a[i]) {
bool res = solve(i+1, j+1, 0);
if (res) {
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||