Submission #577979

#	Time	Username	Problem	Language	Result	Execution time	Memory
577979		dariasc	Building 4 (JOI20_building4)	C++17	11 / 100	2029 ms	27032 KiB

building4

#include <bits/stdc++.h>
using namespace std;
 
#pragma region header
typedef long long ll;
template <typename Value>
using vec = vector<Value>;
istream &in = cin;
ostream &out = cout;
#define all(x) x.begin(), x.end()
#define fast() cin.tie(0); ios_base::sync_with_stdio(0)
#pragma endregion


const int max_n = 2001;
bool dp[2*max_n][max_n+1][2];

void solve()
{
    int n; in >> n;
    vec<int> A(2*n), B(2*n);
    for (int i = 0; i < 2*n; i++) {
        in >> A[i];
    }
    for (int i = 0; i < 2*n; i++) {
        in >> B[i];
    }

    dp[0][1][0] = 1;
    dp[0][0][1] = 1;
    for (int i = 1; i < 2*n; i++) {
        for (int j = 0; j <= n; j++) {
            // A
            if (j > 0) {
                if (A[i] >= A[i-1] && dp[i-1][j-1][0]) {
                    dp[i][j][0] = 1;
                }
                if (A[i] >= B[i-1] && dp[i-1][j-1][1]) {
                    dp[i][j][0] = 1;
                }
            }
            // B
            if (B[i] >= A[i-1] && dp[i-1][j][0]) {
                dp[i][j][1] = 1;
            }
            if (B[i] >= B[i-1] && dp[i-1][j][1]) {
                dp[i][j][1] = 1;
            }
        }
    }

    int at = -1;
    if (dp[2*n-1][n][0]) {
        at = 0;
    } else if (dp[2*n-1][n][1]) {
        at = 1;
    } else {
        out << -1 << endl;
        return;
    }

    int c = n;
    string ans = "";
    for (int i = 2*n-2; i >= 0; i--) {
        if (at == 0) {
            ans.push_back('A');
            c--;
        } else {
            ans.push_back('B');
        }

        if (dp[i][c][0] && dp[i][c][1]) {
            if (A[i] <= B[i] && c > 0) {
                at = 0;
            } else {
                at = 1;
            }
        } else if (dp[i][c][0]) {
            at = 0;
        } else if (dp[i][c][1]) {
            at = 1;
        } else {
            assert(false);
        }
    }
    if (at == 0) {
        ans.push_back('A');
        c--;
    } else {
        ans.push_back('B');
    }
    reverse(all(ans));

    out << ans << endl;
}

int main()
{
    fast();
    solve(); return 0;
    int t; in >> t;
    while (t--) {
        solve();
    }
}

Compilation message (stderr)

building4.cpp:4: warning: ignoring '#pragma region header' [-Wunknown-pragmas]
    4 | #pragma region header
      | 
building4.cpp:12: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   12 | #pragma endregion
      |

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