Submission #378480

#	Time	Username	Problem	Language	Result	Execution time	Memory
378480		morato	Building 4 (JOI20_building4)	C++17	0 / 100	251 ms	126596 KiB

building4

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 2e3 + 5;
const long long INF = 1e18;
 
long long dp[2 * MAXN][MAXN][2];
long long a[2 * MAXN], b[2 * MAXN];
 
string ans;
 
int n;
 
// dp[i][k][f] = melhor soma no prefixo [1, i] se eu escolhi o vetor A k vezes
// e usei o vetor f(0 - A, 1 - B) da ultima vez que peguei um valor
 
long long solve(int i, int k, int f) {
	if (k > n || i - k > n || i > n + n) {
		// cout << i << ' ' << k << ' ' << n << '\n';
		return -INF;
	}
	if (i == n + n) {
		assert(k == n);
		return 0;
	}
	if (dp[i][k][f] != -1) {
		return dp[i][k][f];
	}
	long long opcao1 = 0;
	long long opcao2 = 0;	
	if (i == 0) {
		opcao1 = a[i] + solve(i + 1, k + 1, 0);
		opcao2 = b[i] + solve(i + 1, k, 1);
		return dp[i][k][f] = max(opcao1, opcao2);
	}
	assert(i > 0);
	if (!f) {
		opcao1 = (a[i] >= a[i - 1] ? a[i] + solve(i + 1, k + 1, 0) : -INF);
		opcao2 = (b[i] >= a[i - 1] ? b[i] + solve(i + 1, k, 1) : -INF);
		return dp[i][k][f] = max(opcao1, opcao2);
	}
	opcao1 = (a[i] >= b[i - 1] ? a[i] + solve(i + 1, k + 1, 0) : -INF);
	opcao2 = (b[i] >= b[i - 1] ? b[i] + solve(i + 1, k, 1) : -INF);
	return dp[i][k][f] = max(opcao1, opcao2);
	
}
 
void recu(int i, int k, int f) {
	if (i == n + n) {
		return;
	}
	if (a[i] + solve(i + 1, k + 1, 0) > b[i] + solve(i + 1, k, 1)) {
		ans += 'A';
		recu(i + 1, k + 1, 0);
	} else {
		ans += 'B';
		recu(i + 1, k, 1);
	}
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < 2 * n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < 2 * n; i++) {
		cin >> b[i];
	}
	memset(dp, -1, sizeof dp);
	long long valor = solve(0, 0, 0);
	// cout << valor << '\n';
	if (valor <= 0) {
		cout << -1 << '\n';
	} else {
		recu(0, 0, 0);
		// assert((int) ans.size() == n + n);
		int cnta = 0;
		for (int i = 0; i < 2 * n; i++) {
			cnta += ans[i] == 'A';
		}
		assert(cnta == n);
		cout << ans << '\n';
	}
	return 0;
}

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