Submission #424967

#	Time	Username	Problem	Language	Result	Execution time	Memory
424967		MDario	Building 4 (JOI20_building4)	C++11	0 / 100	1 ms	332 KiB

building4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
ll n, A[1000001], B[1000001];
bool dp[4001][2001][2];
void p(bool zf){
    if(zf==0)cout << 'A';
    else cout << 'B';
    return ;
}
void dfs(ll xf, ll yf, ll zf){
    p(zf);
    if(xf==0){
        return;
    }
    if(zf==0){
        if((A[xf]>=A[xf-1]&&dp[xf-1][yf][0])){
            dfs(xf-1, yf, 0);
            return;
        }
        if((A[xf]>=B[xf-1]&&dp[xf-1][yf][1])){
            dfs(xf-1, yf, 1);
            return;
        }
    }
    else{
        if((B[xf]>=A[xf-1]&&dp[xf-1][yf-1][0])){
            dfs(xf-1, yf-1, 0);
            return;
        }
        if((B[xf]>=B[xf-1]&&dp[xf-1][yf-1][1])){
            dfs(xf-1, yf-1, 1);
            return;
        }
    }
    return ;
}
int main(){
    cin >> n;
    for(int i=0; i<2*n; i++){
        cin >> A[i];
    }
    for(int i=0; i<2*n; i++){
        cin >> B[i];
    }
    dp[0][0][0]=1;
    dp[0][1][1]=1;
    for(int i=1; i<2*n; i++){
        for(int t=0; t<=n; t++){
            if(t>0){
                dp[i][t][1]=((B[i]>=A[i-1]&&dp[i-1][t-1][0])||(B[i]>=B[i-1]&&dp[i-1][t-1][1]));
            }
            dp[i][t][0]=((A[i]>=A[i-1]&&dp[i-1][t][0])||(A[i]>=B[i-1]&&dp[i-1][t][1]));
        }
    }
    if(dp[2*n-1][n][0]){
        dfs(2*n-1, n, 0);
    }
    else if(dp[2*n-1][n][1]){
        dfs(2*n-1, n, 1);
    }
    else{
        cout << -1;
    }
    return 0;
}
/*
2
1 4 10 20
3 5 8 13
*/

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