#pragma GCC optimize ("Ofast") #define _USE_MATH_DEFINES #include <bits/stdc++.h> #define FOR(i, a, b) for (auto i=(a); i<(b); i++) #define FORD(i, a, b) for (int i=(a); i>(b); i--) #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(), (x).end() #define PPC(x) __builtin_popcountll(x) #define MSB(x) (63 - __builtin_clzll(x)) #define LSB(x) __builtin_ctz(x) #define ARG(x, i) (get<i>(x)) #define ithBit(m, i) ((m) >> (i) & 1) #define pb push_back #define ft first #define sd second #define kw(a) ((a) * (a)) #ifdef DEBUG #include "debug.h" #else #define dbg(...) 0 #endif using namespace std; template <typename T1, typename T2> inline void remin(T1& a, T2 b) { a = min(a, (T1)b); } template <typename T1, typename T2> inline void remax(T1& a, T2 b) { a = max(a, (T1)b); } const int maxN = 7900; const long long INF = 200'000'000'000'000; int A[maxN], B[maxN]; long long dp[maxN][maxN]; char out[maxN]; int n, k; bool check(long long x) { FOR(i, 1, n+1) { long long b = dp[i-1][0]; dp[i][0] = b <= x ? max(0ll, B[i] + b) : INF; FOR(j, 1, min(k,i) + 1) { dp[i][j] = INF; long long a = max(0ll, dp[i-1][j-1] + A[i]); long long b = max(0ll, dp[i-1][j] + B[i]); if (dp[i-1][j-1] <= x) remin(dp[i][j], a); if (dp[i-1][j] <= x) remin(dp[i][j], b); } dp[i][i+1] = INF; } return dp[n][k] <= x; } void recover(long long x) { int j = k; FORD(i, n, 0) { bool aneta = j != 0 and dp[i-1][j-1] <= x and dp[i][j] == max(0ll, dp[i-1][j-1] + A[i]); out[i] = aneta ? 'A' : 'B'; j -= aneta; } } void test(long long x) { long long mintail = 0, pref = 0, as = 0; bool juz = false; FOR(i, 1, n+1) { if (out[i] == 'A') as++, pref += A[i]; else pref += B[i]; long long cur = pref - mintail; assert(cur <= x); if (cur == x) juz = true; remin(mintail, pref); } assert(juz or x == 0); assert(as == k); } void solve() { scanf ("%d%d", &n, &k); FOR(i, 1, k+1) dp[0][i] = INF; FOR(i, 1, n+1) scanf ("%d", A+i); FOR(i, 1, n+1) scanf ("%d", B+i); bool snek = k*2 > n; if (snek) { k = n-k; FOR(i, 1, n+1) swap(A[i], B[i]); } long long a = -1ll, b = INF / 2; while (b - a > 1ll) { long long c = (a + b) / 2; (check(c) ? b : a) = c; } check(b); recover(b); printf("%lld\n", b); if (snek) { k = n-k; FOR(i, 1, n+1) out[i] ^= 'A' ^ 'B', swap(A[i], B[i]); } //test(b); printf("%s\n", out + 1); } int main() { int t = 1; //scanf ("%d", &t); FOR(tid, 1, t+1) { //printf("Case #%d: ", tid); solve(); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 | #pragma GCC optimize ("Ofast") #define _USE_MATH_DEFINES #include <bits/stdc++.h> #define FOR(i, a, b) for (auto i=(a); i<(b); i++) #define FORD(i, a, b) for (int i=(a); i>(b); i--) #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(), (x).end() #define PPC(x) __builtin_popcountll(x) #define MSB(x) (63 - __builtin_clzll(x)) #define LSB(x) __builtin_ctz(x) #define ARG(x, i) (get<i>(x)) #define ithBit(m, i) ((m) >> (i) & 1) #define pb push_back #define ft first #define sd second #define kw(a) ((a) * (a)) #ifdef DEBUG #include "debug.h" #else #define dbg(...) 0 #endif using namespace std; template <typename T1, typename T2> inline void remin(T1& a, T2 b) { a = min(a, (T1)b); } template <typename T1, typename T2> inline void remax(T1& a, T2 b) { a = max(a, (T1)b); } const int maxN = 7900; const long long INF = 200'000'000'000'000; int A[maxN], B[maxN]; long long dp[maxN][maxN]; char out[maxN]; int n, k; bool check(long long x) { FOR(i, 1, n+1) { long long b = dp[i-1][0]; dp[i][0] = b <= x ? max(0ll, B[i] + b) : INF; FOR(j, 1, min(k,i) + 1) { dp[i][j] = INF; long long a = max(0ll, dp[i-1][j-1] + A[i]); long long b = max(0ll, dp[i-1][j] + B[i]); if (dp[i-1][j-1] <= x) remin(dp[i][j], a); if (dp[i-1][j] <= x) remin(dp[i][j], b); } dp[i][i+1] = INF; } return dp[n][k] <= x; } void recover(long long x) { int j = k; FORD(i, n, 0) { bool aneta = j != 0 and dp[i-1][j-1] <= x and dp[i][j] == max(0ll, dp[i-1][j-1] + A[i]); out[i] = aneta ? 'A' : 'B'; j -= aneta; } } void test(long long x) { long long mintail = 0, pref = 0, as = 0; bool juz = false; FOR(i, 1, n+1) { if (out[i] == 'A') as++, pref += A[i]; else pref += B[i]; long long cur = pref - mintail; assert(cur <= x); if (cur == x) juz = true; remin(mintail, pref); } assert(juz or x == 0); assert(as == k); } void solve() { scanf ("%d%d", &n, &k); FOR(i, 1, k+1) dp[0][i] = INF; FOR(i, 1, n+1) scanf ("%d", A+i); FOR(i, 1, n+1) scanf ("%d", B+i); bool snek = k*2 > n; if (snek) { k = n-k; FOR(i, 1, n+1) swap(A[i], B[i]); } long long a = -1ll, b = INF / 2; while (b - a > 1ll) { long long c = (a + b) / 2; (check(c) ? b : a) = c; } check(b); recover(b); printf("%lld\n", b); if (snek) { k = n-k; FOR(i, 1, n+1) out[i] ^= 'A' ^ 'B', swap(A[i], B[i]); } //test(b); printf("%s\n", out + 1); } int main() { int t = 1; //scanf ("%d", &t); FOR(tid, 1, t+1) { //printf("Case #%d: ", tid); solve(); } return 0; } |