Submission #378461

#	Time	Username	Problem	Language	Result	Execution time	Memory
378461		morato	Building 4 (JOI20_building4)	C++17	0 / 100	245 ms	126652 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) {
		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, 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 (k > n || i - k > n || 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 {
		ans = "";
		recu(0, 0, 0);
		assert((int) ans.size() == n + n);
		cout << ans << '\n';
	}
	return 0;
}

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