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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

ll best;
int n;
vector<bool>Mask,MaskCopy;
vector<ll>A,B,Selected;
bool lowMode;

void eval() {
    vector<ll>&Pref = Selected;
    ll max_range_sum = 0;
    ll min_so_far = 0;
    for(int i=1;i<=n;i++){
        max_range_sum = max(max_range_sum, Pref[i]-min_so_far);
        min_so_far = min(min_so_far, Pref[i]);
    }
    if (max_range_sum < best) {
        best = max_range_sum;
        copy(Mask.begin(), Mask.end(), MaskCopy.begin());
    }
}

void R(int i, int Aleft, int Bleft) { //lowMode true->Alow, false->Blow
    if (i == n)
        eval();
    else {
        if (Aleft && (!lowMode || A[i]<=B[i])) {
            Mask[i] = true;
            Selected[i+1] = Selected[i] + A[i];
            R(i+1, Aleft-1, Bleft);
        }
        if (Bleft && (lowMode || B[i]<=A[i])) {
            Mask[i] = false;
            Selected[i+1] = Selected[i] + B[i];
            R(i+1, Aleft, Bleft-1);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int k;
    cin >> n >> k;

    A.resize(n);
    B.resize(n);
    for(ll &x : A)
        cin >> x;
    for(ll &x : B)
        cin >> x;

    int Ale=0, Ble=0;
    for(int i=0;i<n;i++){
        if (A[i]<=B[i])
            Ale++;
        if (B[i]<=A[i])
            Ble++;
    }
    
    bool ALowMode = k<=Ale, BLowMode = n-k <= Ble;

    Selected.resize(n+1);
    Mask.resize(n);
    MaskCopy.resize(n);

    best = numeric_limits<ll>::max();
    if (ALowMode) {
        lowMode = true;
        R(0, k, n-k);
    }
    if (BLowMode) {
        lowMode = false;
        R(0, k, n-k);
    }

    cout << best << "\n";
    for(int i=0;i<n;i++)
        cout << (MaskCopy[i]?'A':'B');
    cout << "\n";

    return 0;
}