oj.uz

답안 #651790

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
651790 2022-10-20T03:52:14 Z _HDH 건물 4 (JOI20_building4) C++11
0 / 100
 3 ms 468 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Runtime error 3 ms 468 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 89.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Runtime error 3 ms 468 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -