제출 #626524

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
626524		dxz05	건물 4 (JOI20_building4)	C++14	0 / 100	82 ms	127596 KiB

building4

#include <bits/stdc++.h>

using namespace std;

int p[4004][2002][2];

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

    for (int i = 0; i < 4004; i++){
        for (int j = 0; j < 2002; j++){
            for (int k = 0; k < 2; k++){
                p[i][j][k] = -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] = 0;
                }
                if (dp[1][x - 1] && b[i - 1] <= a[i]){
                    ndp[0][x] = true;
                    p[i][0][x] = 1;
                }
            }

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

        }

        //for (int x = 0; x <= n; x++) cout << (int)ndp[0][x] << ' '; cout << endl;
        //for (int x = 0; x <= n; x++) cout << (int)ndp[1][x] << ' '; cout << endl << endl;

        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 (p[i][j][n] == 0){
            if (j == 0) n--;
            j = 0;
        } else if (p[i][j][n] == 1) {
            if (j == 0) n--;
            j = 1;
        } else {
            assert(false);
        }
        i--;
    }

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

    cout << s << endl;

    return 0;
}

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