Submission #829429

#	Time	Username	Problem	Language	Result	Execution time	Memory
829429		LucaIlie	Building 4 (JOI20_building4)	C++17	11 / 100	66 ms	78176 KiB

building4

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2000;
int a[2 * MAX_N + 1], b[2 * MAX_N + 1], dp[2 * MAX_N + 1][2 * MAX_N + 1][2];

int main() {
    int n;

    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 i = 1; i <= 2 * n; i++ ) {
        for ( int j = 1; j <= i; j++ ) {
            if ( a[i] >= a[i - 1] )
                dp[i][j][0] |= dp[i - 1][j - 1][0];
            if ( a[i] >= b[i - 1] )
                dp[i][j][0] |= dp[i - 1][j - 1][1];
        }
        for ( int j = 0; j <= i; j++ ) {
            if ( b[i] >= a[i - 1] )
                dp[i][j][1] |= dp[i - 1][j][0];
            if ( b[i] >= b[i - 1] )
                dp[i][j][1] |= dp[i - 1][j][1];
        }
    }

    if ( (dp[2 * n][n][0] | dp[2 * n][n][1]) == 0 ) {
        cout << -1;
        return 0;
    }

    vector<char> sol;
    int j = n, lastt = 1e9;
    for ( int i = 2 * n; i >= 1; i-- ) {
        if ( dp[i][j][0] && a[i] <= lastt ) {
            sol.push_back( 'A' );
            lastt = a[i];
            j--;
        } else {
            sol.push_back( 'B' );
            lastt = b[i];
        }
    }

    reverse( sol.begin(), sol.end() );
    for ( char c: sol )
        cout << c;

    return 0;
}

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