제출 #1178127

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178127		VMaksimoski008	Building 4 (JOI20_building4)	C++20	11 / 100	691 ms	589824 KiB

building4

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 1e5 + 5;

signed main() {
    int n; cin >> n;
    int a[2][2*n+1];
    for(int i=0; i<2; i++)
        for(int j=1; j<=2*n; j++) cin >> a[i][j];

    ar<int, 3> par[2*n+1][n+1][2];
    int dp[2*n+1][n+1][2];
    memset(dp, 0, sizeof(dp));

    for(int i=0; i<=2*n; i++)
        for(int j=0; j<=n; j++)
            for(int k=0; k<2; k++) par[i][j][k] = { -1, -1, -1 };

    dp[1][1][0] = 1;
    dp[1][0][1] = 1;

    for(int i=2; i<=2*n; i++) {
        for(int j=0; j<=n; j++) {
            if(j > 1 && dp[i-1][j-1][0] && a[0][i-1] <= a[0][i]) {
                dp[i][j][0] = 1;
                par[i][j][0] = { i-1, j-1, 0 };
            }
            if(j && dp[i-1][j-1][1] && a[1][i-1] <= a[0][i]) {
                dp[i][j][0] = 1;
                par[i][j][0] = { i-1, j-1, 1 };
            }
            if(j && dp[i-1][j][0] && a[0][i-1] <= a[1][i]) {
                dp[i][j][1] = 1;
                par[i][j][1] = { i-1, j, 0 };
            }
            if(dp[i-1][j][1] && a[1][i-1] <= a[1][i]) {
                dp[i][j][1] = 1;
                par[i][j][1] = { i-1, j, 1 };
            }
        }
    }

    if(!dp[2*n][n][0] && !dp[2*n][n][1]) {
        cout << -1 << '\n';
    } else {
        ar<int, 3> curr = { -1, -1, -1 };
        if(dp[2*n][n][0]) curr = { 2*n, n, 0 };
        else curr = { 2*n, n, 1 };
        string ans = "";

        while(curr[0] != -1) {
            auto [i, j, k] = curr;
            if(k == 0) ans += 'A';
            else ans += 'B';
            curr = par[i][j][k];
        }

        reverse(ans.begin(), ans.end());
        cout << ans << '\n';
    }
}

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