| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 651791 | _HDH | Building 4 (JOI20_building4) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) 1001
#endif
using namespace std;
#define all(x) x.begin(), x.end()
#define st first
#define nd second
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define file "TEMPLATE"
typedef long long ll;
typedef pair<int, int> ii;
typedef array<int, 3> iii;
typedef vector<int> vi;
typedef vector<ll> vl;
bool const SINGLE_TEST = 1;
int const N = 2e4 + 1;
ll const INF = LLONG_MIN;
int n;
int arr[N][2];
bool is[N][N][2];
ll dp[N][N][2];
int p[N][N][2];
ll emrua(int i, int cnt, int last){
if (cnt < 0) return INF;
if (i == 2 * n + 1)
return (!cnt? 0: INF);
if (is[i][cnt][last]) return dp[i][cnt][last];
ll x = emrua(i + 1, cnt - 1, 0) + arr[i][0];
if (arr[i - 1][last] > arr[i][0]) x = INF;
ll y = emrua(i + 1, cnt, 1) + arr[i][0];
if (arr[i - 1][last] > arr[i][1]) y = INF;
if (x > y) p[i][cnt][last] = 'A';
else p[i][cnt][last] = 'B';
is[i][cnt][last] = 1;
return dp[i][cnt][last] = max(x, y);
}
void solve(){
cin >> n;
for (int i = 1; i <= 2 * n; i++) cin >> arr[i][0];
for (int j = 1; j <= 2 * n; j++) cin >> arr[j][1];
if (emrua(1, n, 0) < 0){
cout << -1;
return;
}
string ans;
for (int i = 1, j = n, z = 0; i <= 2 * n; i++){
if (p[i][j][z] == 'A')
ans += 'A', j--, z = 0;
else ans += 'B', z = 1;
}
cout << ans;
}
int main(){
ios_base::sync_with_stdio(0);// the
cin.tie(0);cout.tie(0);// magical lines
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
int t;
if (SINGLE_TEST) t = 1;
else cin >> t;
while (t--) solve();
return 0;
}//it's coding time!