#include <stdio.h> #include <algorithm> using namespace std; const int max_size = 1e5; const long long oo = 1e15; #define scan(args...) [&]{ return scanf(args); }(); int n, k; int a[max_size]; int b[max_size]; char answ[max_size+1]; long long solve() /// TO MOŻNA BEZ TABLICY { long long sum[max_size]; long long best = sum[0] = max((answ[0] == 'A' ? a[0] : b[0]), 0); for (int i = 1; i < n; i++) { sum[i] = max(sum[i-1] + (answ[i] == 'A' ? a[i] : b[i]), 0LL); best = max(best, sum[i]); } return best; } int main() { scan("%d%d", &n, &k); for (int i = 0; i < n; i++) scan("%d", &a[i]); for (int i = 0; i < n; i++) scan("%d", &b[i]); for (int i = 0; i < n; i++) answ[i] = 'B'; answ[n] = '\0'; /*long long sum[max_size]; sum[0] = max(b[0], 0); for (int i = 1; i < n; i++) sum[i] = max(sum[i-1] + b[i], 0);*/ long long best = oo; int best_index; for (int o = 0; o < k; o++) { best = oo; for (int i = 0; i < n; i++) if (answ[i] == 'B') { answ[i] = 'A'; long long result = solve(); if (result < best) { best = result; best_index = i; } answ[i] = 'B'; } answ[best_index] = 'A'; } printf("%lld\n%s\n", best, answ); 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 | #include <stdio.h> #include <algorithm> using namespace std; const int max_size = 1e5; const long long oo = 1e15; #define scan(args...) [&]{ return scanf(args); }(); int n, k; int a[max_size]; int b[max_size]; char answ[max_size+1]; long long solve() /// TO MOŻNA BEZ TABLICY { long long sum[max_size]; long long best = sum[0] = max((answ[0] == 'A' ? a[0] : b[0]), 0); for (int i = 1; i < n; i++) { sum[i] = max(sum[i-1] + (answ[i] == 'A' ? a[i] : b[i]), 0LL); best = max(best, sum[i]); } return best; } int main() { scan("%d%d", &n, &k); for (int i = 0; i < n; i++) scan("%d", &a[i]); for (int i = 0; i < n; i++) scan("%d", &b[i]); for (int i = 0; i < n; i++) answ[i] = 'B'; answ[n] = '\0'; /*long long sum[max_size]; sum[0] = max(b[0], 0); for (int i = 1; i < n; i++) sum[i] = max(sum[i-1] + b[i], 0);*/ long long best = oo; int best_index; for (int o = 0; o < k; o++) { best = oo; for (int i = 0; i < n; i++) if (answ[i] == 'B') { answ[i] = 'A'; long long result = solve(); if (result < best) { best = result; best_index = i; } answ[i] = 'B'; } answ[best_index] = 'A'; } printf("%lld\n%s\n", best, answ); return 0; } |