제출 #212166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
212166		KarolloraK	건물 4 (JOI20_building4)	C++17	11 / 100	27 ms	16256 KiB

building4

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int _1[4 * 1000 + 5], _2[4 * 1000 + 5];
bool dyn[4 * 1000 + 5][2][2 * 1000 + 5];

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

    string wyn;
    int n;

    cin >> n;

    for(int i = 1; i < (n << 1) + 1; ++i)
    {
        cin >> _1[i];
    }
    for(int i = 1; i < (n << 1) + 1; ++i)
    {
        cin >> _2[i];
    }

    dyn[1][0][1] = 1;
    dyn[1][1][0] = 1;
    for(int i = 2; i < (n << 1) + 1; ++i)
    {
        for(int j = 0; j < min(i, n) + 1; ++j)
        {
            dyn[i][0][j] = dyn[i - 1][0][j - 1] * (_1[i - 1] <= _1[i]) + dyn[i - 1][1][j - 1] * (_2[i - 1] <= _1[i]);
            dyn[i][1][j] = dyn[i - 1][0][j] * (_1[i - 1] <= _2[i]) + dyn[i - 1][1][j] * (_2[i - 1] <= _2[i]);
        }
    }

    if(dyn[(n << 1)][0][n] + dyn[(n << 1)][1][n] == 0)
    {
        cout << "-1\n";
        return 0;
    }
    for(int i = (n << 1), ile = n; i > 0; --i)
    {
        if(dyn[i][0][ile] == 1 && (wyn.empty() || _1[i] <= (wyn.back() == 'B') * _2[i + 1] + (wyn.back() == 'A') * _1[i + 1]))
        {
            wyn += "A";
            ile--;
        }
        else if(dyn[i][1][ile] == 1)
        {
            wyn += "B";
        }
    }
    reverse(wyn.begin(), wyn.end());
    cout << wyn << "\n";

    return 0;
}

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