#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) {
// 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);
cout << ans << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
126188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
126188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
