Submission #626500

#	Time	Username	Problem	Language	Result	Execution time	Memory
626500		dxz05	Building 4 (JOI20_building4)	C++14	0 / 100	34 ms	63096 KiB

building4

// #include <bits/stdc++.h>
// 
// using namespace std;
// using ll = long long;
// 
// int p[4004][2002][2];
// 
// signed main() {
//     cin.tie(0)->sync_with_stdio(0);
//     
//     int n;
//     cin >> n;
// 
//     vector<int> arr[2];
//     arr[0] = vector<int>(n*2);
//     for (int i = 0; i < n*2; i++) {
//         cin >> arr[0][i];
//     }
//     for (int i = 0; i < n * 2; i++) {
//         cin >> arr[1][i];
//     }
//     
//     int memo[n*2][n+1][2];
//     int par[n*2][n+1][2];
//     memset(memo, -1, sizeof(memo));
// 
//     auto dp = [&](int i, int count, bool last) {
//         if (memo[i][count][last] !=-1) return memo[i][count][last];
//         if (i == n*2) return count == n;
//         if (arr[last][i-1] <= arr[1][i] && dp(i+1, count, 1)) {
//             par[i][count][last] = 1;
//             return memo[i][count][last] = true;
//         }
//         if (arr[last][i-1] <= arr[0][i] && dp(i+1, count+1, 0)) {
//             par[i][count][last] = 2;
//             return memo[i][count][last] = true;
//         }
//         return memo[i][count][last] = false;
//     }
// 
//     dp(
// 
//     return 0;
// }
#include <bits/stdc++.h>
 
using namespace std;
 
int p[4004][2002][2];
 
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n;
    cin >> n;
    
    memset(p, -1, sizeof(p));

    vector<int> a(2*n), b(2*n);
    for (int &i : a) cin >> i;
    for (int &i : b) cin >> i;
 
    vector<vector<char>> dp(2, vector<char>(n + 1));
 
    dp[0][1] = true;
    dp[1][0] = true;
    for (int i = 1; i < 2 * n; i++){
        vector<vector<char>> ndp(2, vector<char>(n + 1));
        
        for (int x = 0; x <= min(n, i + 1); x++){
            // c[i] = a[i]
            if (x > 0){
                if (dp[0][x - 1] && a[i - 1] <= a[i]){
                    ndp[0][x] = true;
                    p[i][0][x] = 0;
                }
                if (dp[1][x - 1] && b[i - 1] <= a[i]){
                    ndp[0][x] = true;
                    p[i][0][x] = 1;
                }
            }
            
            // c[i] = b[i];
            if (dp[0][x] && a[i - 1] <= b[i]){
                ndp[1][x] = true;
                p[i][1][x] = 0;
            }
            if (dp[1][x] && b[i - 1] <= b[i]){
                ndp[1][x] = true;
                p[i][1][x] = 1;
            }
 
        }
 
        //for (int x = 0; x <= n; x++) cout << (int)ndp[0][x] << ' '; cout << endl;  
        //for (int x = 0; x <= n; x++) cout << (int)ndp[1][x] << ' '; cout << endl << endl;  
 
        dp = ndp;
    }
 
    if (!dp[0][n] && !dp[1][n]){
        cout << "-1" << endl;
        return 0;
    }
 
    int i = 2 * n - 1;
    int j = (dp[0][n] ? 0 : 1);
 
    string s;
    while (i >= 0){
        s.push_back('A' + (j != 0));
        if (p[i][j][n] == 0){
            if (j == 0) n--;
            j = 0;
        } else {
            if (j == 0) n--;
            j = 1;
        }
        i--;
    }
 
    reverse(s.begin(), s.end());
 
    cout << s << endl;
 
    return 0;
}
	

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