Submission #651790

#	Time	Username	Problem	Language	Result	Execution time	Memory
651790		_HDH	Building 4 (JOI20_building4)	C++11	0 / 100	3 ms	468 KiB

building4

#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 = 2e3 + 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!

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