Submission #574531

#	Time	Username	Problem	Language	Result	Execution time	Memory
574531		snokes	Building 4 (JOI20_building4)	C++17	0 / 100	555 ms	481736 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vt vector
#define pb push_back
#define sz(x) int((x).size())

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    vt<int> A(2 * N + 1), B(2 * N + 1);
    for(int i = 1; i <= 2 * N; i++) cin >> A[i];
    for(int i = 1; i <= 2 * N; i++) cin >> B[i];

    vt<vt<vt<bool>>> dp(2 * N + 1, vt<vt<bool>>(N + 1, vt<bool>(2)));
    dp[0][0] = {true, true};

    for(int i = 1; i <= 2 * N; i++)
    {
        int curA = A[i], curB = B[i];
        int prevA = A[i - 1], prevB = B[i - 1];
        for(int j = 0; j <= N; j++)
        {
            if(j > 0) dp[i][j][0] = (curA >= prevA && dp[i - 1][j - 1][0]) || (curA >= prevB && dp[i - 1][j - 1][1]);
            dp[i][j][1] = (curB >= prevA && dp[i - 1][j][0]) || (curB >= prevB && dp[i - 1][j][1]);
        }
    }

    int curIdx = 0;
    while(curIdx < 2 && !dp[2 * N][N][curIdx]) curIdx++;

    if(curIdx >= 2)
    {
        cout << -1 << "\n";
        return 0;
    }

    string ans = "";
    for(int i = 2 * N, j = N; i > 0; i--)
    {
        ans += curIdx ? "B" : "A";
        j -= curIdx == 0;
        if(dp[i - 1][j][0]) curIdx = 0;
        else if(dp[i - 1][j][1]) curIdx = 1;
        else assert(false);
    }

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

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