Submission #824980

#	Time	Username	Problem	Language	Result	Execution time	Memory
824980		phoenix	Building 4 (JOI20_building4)	C++17	100 / 100	204 ms	45624 KiB

building4

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    int a[2 * n][2];
    for(int i = 0; i < 2 * n; i++)  
        cin >> a[i][0];
    for(int i = 0; i < 2 * n; i++)  
        cin >> a[i][1];
    pair<int, int> dp[2 * n][2];
    dp[0][0] = {0, 0};
    dp[0][1] = {1, 1};
    for(int i = 1; i < 2 * n; i++) {
        dp[i][0] = dp[i][1] = {2 * n + 1, -1};
        for(int t = 0; t <= 1; t++) {
            for(int p = 0; p <= 1; p++) {
                if(a[i][t] >= a[i - 1][p]) {
                    dp[i][t].first = min(dp[i][t].first, dp[i - 1][p].first + t);
                    dp[i][t].second = max(dp[i][t].second, dp[i - 1][p].second + t);
                }
            }
        }
    }
    int it = -1, k = n;
    for(int t = 0; t <= 1; t++) {
        if(dp[2 * n - 1][t].first <= n && n <= dp[2 * n - 1][t].second) {
            it = t;
            break;
        }
    }
    if(it == -1) {
        cout << -1;
        return 0;
    }
    string res;
    for(int i = 2 * n - 1; i >= 0; i--) {
        res += (it ? 'B' : 'A');
        if(!i) break;
        for(int p = 0; p <= 1; p++) {
            if(a[i][it] >= a[i - 1][p] && (dp[i - 1][p].first <= k - it && k - it <= dp[i - 1][p].second)) {
                k -= it;
                it = p;
                break;
            }
        }
    }
    reverse(res.begin(), res.end());
    cout << res;
}

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