Submission #626533

#	Time	Username	Problem	Language	Result	Execution time	Memory
626533		dxz05	Building 4 (JOI20_building4)	C++14	11 / 100	2013 ms	155328 KiB

building4

#include <bits/stdc++.h>

using namespace std;

pair<int, int> p[4004][2][2002];

int main() {
    cin.tie(0)->sync_with_stdio(0);

    for (int i = 0; i < 4004; i++){
        for (int k = 0; k < 2; k++){
            for (int j = 0; j < 2002; j++){
                p[i][k][j] = make_pair(-1, -1);
            }
        }
    }

    int n;
    cin >> n;

    vector<int> a(2 * n), b(2 * n);
    for (int &i : a) cin >> i;
    for (int &i : b) cin >> i;

    vector<vector<char>> dp(2, vector<char>(n + 1));

    dp[0][1] = true;
    dp[1][0] = true;
    for (int i = 1; i < 2 * n; i++){
        vector<vector<char>> ndp(2, vector<char>(n + 1));

        for (int x = 0; x <= min(n, i + 1); x++){
            // c[i] = a[i]
            if (x > 0){
                if (dp[0][x - 1] && a[i - 1] <= a[i]){
                    ndp[0][x] = true;
                    p[i][0][x] = make_pair(0, x - 1);
                }
                if (dp[1][x - 1] && b[i - 1] <= a[i]){
                    ndp[0][x] = true;
                    p[i][0][x] = make_pair(1, x - 1);
                }
            }

            // c[i] = b[i];
            if (dp[0][x] && a[i - 1] <= b[i]){
                ndp[1][x] = true;
                p[i][1][x] = make_pair(0, x);
            }
            if (dp[1][x] && b[i - 1] <= b[i]){
                ndp[1][x] = true;
                p[i][1][x] = make_pair(1, x);
            }

        }

        dp = ndp;
    }

    if (!dp[0][n] && !dp[1][n]){
        cout << "-1" << endl;
        return 0;
    }

    int i = 2 * n - 1;
    int j = (dp[0][n] ? 0 : 1);

    string s;
    while (i >= 0){
        s.push_back('A' + (j != 0));
        if (i > 0 && p[i][j][n] == make_pair(-1, -1)){
            assert(false);
        }
        pair<int, int> pp = p[i][j][n];
        j = pp.first;
        n = pp.second;
        i--;
    }

    reverse(s.begin(), s.end());

    cout << s << endl;

    return 0;
}

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