Submission #1026533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026533		overwatch9	Building 4 (JOI20_building4)	C++17	11 / 100	2669 ms	524288 KiB

building4

#include <bits/stdc++.h>
using namespace std;
int n;
vector <int> a, b;
// let dp[i][j][2] be the smallest end position(i)
// 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) {
                ans = res;
                goes_to[i][j][lst] = {i+1, j+1, 0};
            }
        }
    }
    // choose plan b now
    if (lst == 0 && a[i-1] <= b[i]) {
        bool res = solve(i+1, j, 1);
        if (res) {
            ans = res;
            goes_to[i][j][lst] = {i+1, j, 1};
        }
    }
    if (lst == 1 && b[i-1] <= b[i]) {
        bool res = solve(i+1, j, 1);
        if (res) {
            ans = res;
            goes_to[i][j][lst] = {i+1, j, 1};
        }
    }
    dp[i][j][lst] = ans;
    ready[i][j][lst] = true;
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    n *= 2;
    a = b = vector <int> (n+1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    if (!solve(1, 0, 0)) {
        cout << -1 << '\n';
        return 0;
    }
    array <int, 3> cur = {1, 0, 0};
    while (cur[0] <= n) {
        array <int, 3> nxt = goes_to[cur[0]][cur[1]][cur[2]];
        if (nxt[1] == cur[1] + 1)
            cout << 'A';
        else
            cout << 'B';
        cur = nxt;
    }
    cout << '\n';
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 89