#include <stdio.h> #include <bitset> #define MAX(a,b) (((a)>(b))?(a):(b)) using ll=long long; const int C=100001, D=10001, Inf=1000000001; ll a[C], b[C], dp[C], tmp_dp[C]; std::bitset<D> res[C]; bool exists[C], tmp_exists[C]; bool check_validity(ll m, int n, int k){ int i, j; for (j=0; j<=k; j++) exists[j] = false, tmp_exists[j]=false; exists[0]=true; dp[0]=0; for (i=1; i<=n; i++){ for (j=0; j<=k; j++){ if (exists[j] && dp[j]+b[i] <= m){ tmp_exists[j] = true; tmp_dp[j] = MAX(dp[j]+b[i], 0); res[i][j] = 0; } if (j>0 && exists[j-1] && dp[j-1]+a[i] <= m && ((!tmp_exists[j]) || (dp[j-1]+a[i] < tmp_dp[j]))){ tmp_exists[j] = true; tmp_dp[j] = MAX(dp[j-1]+a[i], 0); res[i][j] = true; } } for (j=0; j<=k; j++){ dp[j] = tmp_dp[j]; exists[j] = tmp_exists[j]; tmp_exists[j] = false; } } return exists[k]; } int to_fill[C]; int main(){ int n, k, i; bool inv=false; scanf ("%d %d", &n, &k); if (k > n/2) inv=true, k=n-k; if (!inv){ for (i=1; i<=n; i++) scanf ("%lld", &a[i]); for (i=1; i<=n; i++) scanf ("%lld", &b[i]); } else{ for (i=1; i<=n; i++) scanf ("%lld", &b[i]); for (i=1; i<=n; i++) scanf ("%lld", &a[i]); } ll l=0, r=1ll*n*Inf, m; while (l<=r){ m = (l+r)/2; if (check_validity(m, n, k)) r=m-1; else l=m+1; } ll vv = l; int cur=k; printf ("%lld\n", vv); check_validity(vv, n, k); for (i=n; i>0; i--) { to_fill[i] = res[i][cur]; cur = cur-to_fill[i]; } if (!inv){ for (i=1; i<=n; i++) printf ("%c", ((to_fill[i]==0)?('B'):('A'))); } else{ for (i=1; i<=n; i++) printf ("%c", ((to_fill[i]==0)?('A'):('B'))); } printf ("\n"); 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 | #include <stdio.h> #include <bitset> #define MAX(a,b) (((a)>(b))?(a):(b)) using ll=long long; const int C=100001, D=10001, Inf=1000000001; ll a[C], b[C], dp[C], tmp_dp[C]; std::bitset<D> res[C]; bool exists[C], tmp_exists[C]; bool check_validity(ll m, int n, int k){ int i, j; for (j=0; j<=k; j++) exists[j] = false, tmp_exists[j]=false; exists[0]=true; dp[0]=0; for (i=1; i<=n; i++){ for (j=0; j<=k; j++){ if (exists[j] && dp[j]+b[i] <= m){ tmp_exists[j] = true; tmp_dp[j] = MAX(dp[j]+b[i], 0); res[i][j] = 0; } if (j>0 && exists[j-1] && dp[j-1]+a[i] <= m && ((!tmp_exists[j]) || (dp[j-1]+a[i] < tmp_dp[j]))){ tmp_exists[j] = true; tmp_dp[j] = MAX(dp[j-1]+a[i], 0); res[i][j] = true; } } for (j=0; j<=k; j++){ dp[j] = tmp_dp[j]; exists[j] = tmp_exists[j]; tmp_exists[j] = false; } } return exists[k]; } int to_fill[C]; int main(){ int n, k, i; bool inv=false; scanf ("%d %d", &n, &k); if (k > n/2) inv=true, k=n-k; if (!inv){ for (i=1; i<=n; i++) scanf ("%lld", &a[i]); for (i=1; i<=n; i++) scanf ("%lld", &b[i]); } else{ for (i=1; i<=n; i++) scanf ("%lld", &b[i]); for (i=1; i<=n; i++) scanf ("%lld", &a[i]); } ll l=0, r=1ll*n*Inf, m; while (l<=r){ m = (l+r)/2; if (check_validity(m, n, k)) r=m-1; else l=m+1; } ll vv = l; int cur=k; printf ("%lld\n", vv); check_validity(vv, n, k); for (i=n; i>0; i--) { to_fill[i] = res[i][cur]; cur = cur-to_fill[i]; } if (!inv){ for (i=1; i<=n; i++) printf ("%c", ((to_fill[i]==0)?('B'):('A'))); } else{ for (i=1; i<=n; i++) printf ("%c", ((to_fill[i]==0)?('A'):('B'))); } printf ("\n"); return 0;} |