Submission #379411

#TimeUsernameProblemLanguageResultExecution timeMemory
379411Jarif_RahmanBuilding 4 (JOI20_building4)C++17
0 / 100
1 ms364 KiB
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int inf = 1e9 + 9;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    vector<int> a(2*n), b(2*n);
    for(int &x: a) cin >> x;
    for(int &x: b) cin >> x;
    vector<vector<int>> dp(2*n, vector<int>(n+1, -1));
    dp[0][0] = b[0];
    dp[0][1] = a[0];
    for(int i = 1; i < 2*n; i++){
        for(int j = 0; j <= n; j++){
            int x = inf;
            if(dp[i-1][j] != -1 && b[i] >= dp[i-1][j]) x = min(x, b[i]);
            if(j > 0 && dp[i-1][j-1] != -1 && a[i] >= dp[i-1][j-1]) x = min(x, a[i]);
            dp[i][j] = (x == inf ? -1:x);
        }
    }
    for(int i = 0; i < 2*n; i++){
        for(int j = 0; j <= n; j++) cerr << dp[i][j] << " ";
        cerr << "\n";
    }
    if(dp[2*n-1][n] == -1){
        cout << "-1\n";
        exit(0);
    }
    str ans = "";
    int cur = n;
    for(int i = 2*n-1; i > 0; i--){
        if(dp[i][cur] >= dp[i-1][cur] && dp[i-1][cur] != -1) ans+="B";
        else{
            ans+="A";
            cur--;
        }
    }
    ans+=(cur == 1 ? "A":"B");
    reverse(ans.begin(), ans.end());
    cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...