Submission #1253943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253943		tvgk	건물 4 (JOI20_building4)	C++20	100 / 100	142 ms	41688 KiB

building4

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e6 + 7, inf = 1e9 + 7;

int a[mxN][2], n;
ii dp[mxN][2];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

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

    for (int j = 1; j <= n * 2; j++)
    {
        for (int i = 0; i <= 2; i++)
        {
            dp[j][i] = {inf, -inf};

            for (int u = 0; u <= 1; u++)
            {
                if (a[j - 1][u] <= a[j][i])
                {
                    dp[j][i].fi = min(dp[j][i].fi, dp[j - 1][u].fi + i);
                    dp[j][i].se = max(dp[j][i].se, dp[j - 1][u].se + i);
                }
            }
        }
    }

    if (!(dp[n * 2][0].fi <= n && n <= dp[n * 2][0].se) && !(dp[n * 2][1].fi <= n && n <= dp[n * 2][1].se))
    {
        cout << -1;
        return 0;
    }

    bool cur = 0;
    int cnt = n;
    a[n * 2 + 1][0] = inf;
    string ans;
    for (int i = n * 2; i >= 1; i--)
    {
        for (int j = 0; j <= 1; j++)
        {
            if (a[i + 1][cur] >= a[i][j] && dp[i][j].fi <= cnt && cnt <= dp[i][j].se)
            {
                cur = j;
                break;
            }
        }
        ans += 'A' + cur;
        cnt -= cur;
    }

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

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