Submission #709550

#	Time	Username	Problem	Language	Result	Execution time	Memory
709550		RandomLB	Building 4 (JOI20_building4)	C++17	11 / 100	96 ms	91140 KiB

building4

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
#define all(x) x.begin(), x.end()
#define ms(x, a) memset(x, a, sizeof(x))
//===========================================
const int MAX = 4005;
int a[MAX], b[MAX], dp[2][MAX][MAX];

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n; n*=2;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    dp[0][0][0] = -1;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= n; j++){
            if (j && a[i] >= a[i-1] && dp[0][i-1][j-1])
                dp[0][i][j] = 1;
            if (j && a[i] >= b[i-1] && dp[1][i-1][j-1])
                dp[0][i][j] = 2;
            if (b[i] >= a[i-1] && dp[0][i-1][j])
                dp[1][i][j] = 1;
            if (b[i] >= b[i-1] && dp[1][i-1][j])
                dp[1][i][j] = 2;
        }
    }
    if (dp[0][n][n/2] || dp[1][n][n/2]){
        string res = "";
        int c = (dp[0][n][n/2]? 0 : 1), rem = n/2;
        for (int i = n; i; i--){
            res += (c? 'B' : 'A');
            c = dp[c][i][rem]-1;
            if (res.back() == 'A') rem--;
        }
        reverse(all(res));
        cout << res << "\n";
        return 0;
    }
    cout << -1 << "\n";
}

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