Submission #1291232

#TimeUsernameProblemLanguageResultExecution timeMemory
1291232haha건물 4 (JOI20_building4)C++20
0 / 100
118 ms252240 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e3+5;
const ll MOD=1e9+7;
const int base=31;

int n;
int a[maxn],b[maxn];
string dp[maxn][maxn][2];
// 0 A
// 1 B
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=2*n;i++) cin>>a[i];
    for(int i=1;i<=2*n;i++) cin>>b[i];
    for(int i=1;i<=2*n;i++){
        for(int j=1;j<=i;j++){
            if(a[i]>=a[i-1]){
                if(dp[j-1][i-j][0].size()==i-1) dp[j][i-j][0]=dp[j-1][i-j][0]+"A";
            }
            if(a[i]>=b[i-1]){
                if(dp[j-1][i-j][1].size()==i-1) dp[j][i-j][0]=dp[j-1][i-j][1]+"A";
            }
            if(b[i]>=b[i-1]){
                if(dp[i-j][j-1][1].size()==i-1) dp[i-j][j][1]=dp[i-j][j-1][1]+"B";
            }
            if(b[i]>=a[i-1]){
                if(dp[i-j][j-1][0].size()==i-1) dp[i-j][j][1]=dp[i-j][j-1][0]+"B";
            }
        }
    }
    string ans="-1";
    if(!dp[n][n][0].empty()) ans=dp[n][n][0];
    if(!dp[n][n][1].empty()) ans=dp[n][n][1];
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...