제출 #1291478

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

building4

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 5e3 + 10;

int n;
int a[2 * MAXN][2];

bool dp[2 * MAXN][2][MAXN];

vector < int > ans;

void read()
{
    cin >> n;

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

void rec(int pos, int cur, int cnt)
{
    if(pos == 0)
        return;

    ans.push_back(cur);

    for(int y = 0; y < 2; y++)
    {
        if(a[pos - 1][y] <= a[pos][cur] && dp[pos - 1][y][cnt - cur])
        {
            rec(pos - 1, y, cnt - cur);
            break;
        }
    }
}

void solve()
{
    dp[0][0][0] = 1;
    for(int i = 1; i <= 2 * n; i++)
    {
        for(int x = 0; x < 2; x++)
        {
            for(int j = 0; j <= min(i, n); j++)
            {
                for(int y = 0; y < 2; y++)
                {
                    if(a[i - 1][y] <= a[i][x] && j - x >= 0 && i - 1 >= j - x)
                    {
                        dp[i][x][j] = dp[i][x][j] | dp[i - 1][y][j - x];
                    }
                }
            }
        }
    }

    if(dp[2 * n][0][n])
    {
        rec(2 * n, 0, n);

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

        for(int x : ans)
        {
            cout << (char)('A' + x);
        }

        cout << endl;
    }
    else if(dp[2 * n][1][n])
    {
        rec(2 * n, 1, n);

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

        for(int x : ans)
        {
            cout << (char)('A' + x);
        }

        cout << endl;
    }
    else 
    {
        cout << "-1" << endl;
    }
}

int main()
{
    read();
    solve();

    return 0;
}

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