Submission #756936

#TimeUsernameProblemLanguageResultExecution timeMemory
756936Dan4LifeBuilding 4 (JOI20_building4)C++17
11 / 100
43 ms16180 KiB
#include <bits/stdc++.h>
using namespace std;
const int mxN = (int)2e3+10;
int n, a[2][mxN*2];
bool dp[mxN*2][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] and j>=!!k) 
                        dp[i][j][k]|=dp[i-1][j-!!k][l];
    int tot = n, p=(int)1e9+10; 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;
            }
        }
        if(i==2*n and ans.empty()){cout<<-1;return 0;}
    }
    reverse(begin(ans),end(ans)); cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...