제출 #756910

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
756910		Dan4Life	건물 4 (JOI20_building4)	C++17	0 / 100	1 ms	212 KiB

building4

#include <bits/stdc++.h>
using namespace std;
const int mxN = (int)2e3+10;
int n, a[2][mxN];
bool dp[mxN][mxN][2];

int main(){
    cin >> n;
    for(int i = 1; i<=2*n; i++) cin >> a[0][i];
    for(int i = 1; i<=2*n; i++) cin >> a[1][i];
    dp[1][0][0]=dp[1][1][1] = 1;
    for(int i = 2; i <= 2*n; i++){
        for(int j = 0; j <= n; j++){
            for(int k = 0; k < 2; k++){
                for(int l = 0; l < 2; l++){
                    if(a[l][i-1]<=a[k][i]) dp[i][j][k]|=dp[i-1][j-!!k][l];
                }
            }
        }
    }
    int tot = n,p=(int)1e9; string ans = "";
    for(int i = 2*n; i; i--){
        for(int k = 0; k < 2; k++){
            if(dp[i][tot][k] and a[k][i]<=p){
                tot-=!!k; ans+=(k?'B':'A'); p=a[k][i]; break;
            }
        }
    }
    reverse(begin(ans),end(ans));
    cout << ans << "\n";
}

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