Submission #937699

#	Time	Username	Problem	Language	Result	Execution time	Memory
937699		borisAngelov	Building 4 (JOI20_building4)	C++17	11 / 100	2076 ms	405632 KiB

building4

#include <bits/stdc++.h>

using namespace std;

const int maxn = 4005;

int n;

int a[maxn];
int b[maxn];

bool dp[maxn][maxn][2];
tuple<int, int, int> prv[maxn][maxn][2];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

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

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

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

    for (int pos = 1; pos <= 2 * n; ++pos)
    {
        for (int cntA = 0; cntA <= n; ++cntA)
        {
            if (b[pos] >= b[pos - 1])
            {
                dp[pos][cntA][1] |= dp[pos - 1][cntA][1];

                if (dp[pos - 1][cntA][1] == true)
                {
                    prv[pos][cntA][1] = make_tuple(pos - 1, cntA, 1);
                }
            }

            if (b[pos] >= a[pos - 1])
            {
                dp[pos][cntA][1] |= dp[pos - 1][cntA][0];

                if (dp[pos - 1][cntA][0] == true)
                {
                    prv[pos][cntA][1] = make_tuple(pos - 1, cntA, 0);
                }
            }

            if (a[pos] >= a[pos - 1] && cntA >= 1)
            {
                dp[pos][cntA][0] |= dp[pos - 1][cntA - 1][0];

                if (dp[pos - 1][cntA - 1][0] == true)
                {
                    prv[pos][cntA][0] = make_tuple(pos - 1, cntA - 1, 0);
                }
            }

            if (a[pos] >= b[pos - 1] && cntA >= 1)
            {
                dp[pos][cntA][0] |= dp[pos - 1][cntA - 1][1];

                if (dp[pos - 1][cntA - 1][1] == true)
                {
                    prv[pos][cntA][0] = make_tuple(pos - 1, cntA - 1, 1);
                }
            }
        }
    }

    bool hasAns = (dp[2 * n][n][0] == true || dp[2 * n][n][1] == true);

    if (hasAns == false)
    {
        cout << -1 << endl;
    }
    else
    {
        int pos = 2 * n;
        int curr = (dp[2 * n][n][0] == true ? 0 : 1);
        int cntA = n;

        stack<char> result;

        while (pos >= 1)
        {
            result.push(char(curr + 'A'));
            tie(pos, cntA, curr) = prv[pos][cntA][curr];
        }

        while (!result.empty())
        {
            cout << result.top();
            result.pop();
        }

        cout << endl;
    }

    return 0;
}

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