Submission #379413

#	Time	Username	Problem	Language	Result	Execution time	Memory
379413		Jarif_Rahman	Building 4 (JOI20_building4)	C++17	11 / 100	494 ms	524292 KiB

building4

#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);
        }
    }
    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 && dp[i][cur] == b[i]) ans+="B";
        else{
            ans+="A";
            cur--;
        }
    }
    ans+=(cur == 1 ? "A":"B");
    reverse(ans.begin(), ans.end());
    cout << ans << "\n";
}

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