이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |