Submission #424973

#	Time	Username	Problem	Language	Result	Execution time	Memory
424973		MDario	Building 4 (JOI20_building4)	C++11	11 / 100	2015 ms	36884 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){
    if(xf==0){
        p(zf);
        return;
    }
    if(zf==0){
        if((A[xf]>=A[xf-1]&&dp[xf-1][yf][0])){
            dfs(xf-1, yf, 0);
        }
        else if((A[xf]>=B[xf-1]&&dp[xf-1][yf][1])){
            dfs(xf-1, yf, 1);
        }
    }
    else{
        if((B[xf]>=A[xf-1]&&dp[xf-1][yf-1][0])){
            dfs(xf-1, yf-1, 0);
        }
        else if((B[xf]>=B[xf-1]&&dp[xf-1][yf-1][1])){
            dfs(xf-1, yf-1, 1);
        }
    }
    p(zf);
    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;
}
/*
3
2 5 4 9 15 11
6 7 6 8 12 14
*/

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