Submission #1340019

#TimeUsernameProblemLanguageResultExecution timeMemory
1340019hoangtien69건물 4 (JOI20_building4)C++20
0 / 100
23 ms31812 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 4005;
const int INF = 1e9 + 5;

int n;
int a[MAXN];
int b[MAXN];
bool dp[MAXN][MAXN][2];
vector<char> peal;

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

    cin >> n;
    for (int i = 1; i <= 2 * n; i++) cin >> a[i];
    for (int i = 1; i <= 2 * n; i++) cin >> b[i];

    a[0] = -INF;
    b[0] = -INF;
    memset(dp, false, sizeof dp);
    dp[0][0][0] = true;
    dp[0][0][1] = true;

    for (int i = 1; i <= 2 * n; i++)
    {
        for (int j = 0; j <= min(n, i); j++)
        {
            if (j >= 1)
            {
                if (a[i-1] <= a[i] && dp[i-1][j-1][0]) dp[i][j][0] = true;
                if (b[i-1] <= a[i] && dp[i-1][j-1][1]) dp[i][j][0] = true;
            }
            if (a[i-1] <= b[i] && dp[i-1][j][0]) dp[i][j][1] = true;
            if (b[i-1] <= b[i] && dp[i-1][j][1]) dp[i][j][1] = true;
        }
    }
    if (!dp[2*n][n][0] && !dp[2*n][n][1])
    {
        cout << -1;
        return 0;
    }
    int i = 2 * n, j = n, last = dp[2*n][n][0] ? 0 : 1;
    while (i > 0)
    {
        if (last == 0)
        {
            peal.push_back('A');
            i--;
            j--;
            if (dp[i][j][0]) last = 0;
            else last = 1;
        }
        else
        {
            peal.push_back('B');
            i--;
            if (dp[i][j][0]) last = 0;
            else last = 1;
        }
    }
    reverse(peal.begin(), peal.end());
    for (char v : peal) cout << v;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...