제출 #211511

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
211511		popovicirobert	Building 4 (JOI20_building4)	C++14	100 / 100	333 ms	26136 KiB

building4

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x))

using namespace std;

const int MAXN = (int)1e6;

int arr[2 * MAXN + 1];
pair<int, int> dp[2 * MAXN + 1];

int main() {
#ifdef HOME
	ifstream cin("C.in");
	ofstream cout("C.out");
#endif
	int i, j, n;
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	n *= 2;
	for(i = 1; i <= n; i++) {
		cin >> arr[2 * i - 1];
	}
	for(i = 1; i <= n; i++) {
		cin >> arr[2 * i];
	}
	for(i = 1; i <= 2 * n; i++) {
		dp[i].first = 2 * n;
		dp[i].second = -2 * n;
		int cur = 1;
		if(i % 2 == 0) {
			cur = -1;
		}
		for(j = i - 1; j >= max(0, i - 3); j--) {
			if((i + 1) / 2 - (j + 1) / 2 == 1 && arr[j] <= arr[i]) {
				dp[i].first = min(dp[i].first, dp[j].first + cur);
				dp[i].second = max(dp[i].second, dp[j].second + cur);
			}
		}
		//cerr << arr[i] << " " << dp[i].first << " " << dp[i].second << "\n";
	}
	string str;
	int pos = 2 * n;
	if(dp[2 * n - 1].first <= 0 && dp[2 * n - 1].second >= 0) {
		pos = 2 * n - 1;
	}
	if(dp[pos].first > 0 || dp[pos].second < 0) {
		cout << -1;
		return 0;
	}
	int val = 0;
	while(pos != 0) {
		int cur = 1;
		if(pos & 1) {
			str += 'A';
		}
		else {
			str += 'B';
			cur = -1;
		}
		//cerr << pos << "\n";
		for(j = pos - 1; j >= max(0, pos - 3); j--) {
			if(arr[pos] >= arr[j] && (pos + 1) / 2 - (j + 1) / 2 == 1 && dp[j].first + cur <= val && dp[j].second + cur >= val) {
				pos = j, val -= cur;
				break;
			}
		}
	}
	reverse(str.begin(), str.end());
	cout << str;

	return 0;
}

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