Submission #1201674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201674		g4yuhg	Building 4 (JOI20_building4)	C++20	11 / 100	253 ms	141048 KiB

building4

#include<bits/stdc++.h>
typedef long long ll;
#define fi first
#define se second
#define pii pair<ll,ll>
#define inf 1e9
#define N 1000006
using namespace std;
ll n, m;
ll a[N], b[N], dd[N];
ll f[4002][2002][2];
ll dp(ll i, ll j, ll tt) {
	if (i > n * 2) {
		if (j == n) {
			return 1;
		}
		return 0;
	}
	if (f[i][j][tt] != -1) {
		return f[i][j][tt];
	}
	ll last = a[i - 1];
	if (tt == 1) {
		last = b[i - 1];
	}
	ll res = 0;
	if (a[i] >= last && j <= n) {
		res = max(res, dp(i + 1, j + 1, 0));
	}
	if (b[i] >= last) {
		res = max(res, dp(i + 1, j, 1) );
	}
	f[i][j][tt] = res;
	return res;
}
void trace(ll i, ll j, ll tt) {
	if (i > n * 2) {
		return;
	}
	ll last = a[i - 1];
	if (tt == 1) {
		last = b[i - 1];
	}
	if (a[i] >= last && j <= n) {
		//res = max(res, dp(i + 1, j + 1, 0));
		if (dp(i + 1, j + 1, 0) == 1) {
			dd[i] = 1;
			trace(i + 1, j + 1, 0);
			return;
		}
	}
	if (b[i] >= last) {
		//res = max(res, dp(i + 1, j, 1) );
		if (dp(i + 1, j, 1) == 1) {
			trace(i + 1, j, 1);
			return;
		}
	}
}
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n + n; i ++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n + n; i ++) {
		cin >> b[i];
	}
	memset(f, -1, sizeof(f));
	ll x = dp(1, 0, 0);
	if (x == 0) {
		cout << -1;
		return 0;
	}
	trace(1, 0, 0);
	for (int i = 1; i <= n + n; i ++) {
		if (dd[i]) {
			cout << "A";
		}
		else {
			cout << "B";
		}
	}
	return 0;
}

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