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
140
141
142
143
144
145
146
147
148
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
ll pot(ll x){
    ll tmp = 1;
    while(x){
        x/=2;
        tmp*=2;
    }
    return tmp;
}
 
ll treeSize;
vector<ll> pref, suf, maxSum, sum;
ll n, m;
 
void buildTree(){
    treeSize = pot(n);
    pref.resize(treeSize*2+2);
    suf.resize(treeSize*2+2);
    maxSum.resize(treeSize*2+2);
    sum.resize(treeSize*2+2);
}
 
void buduj(){
    for(ll i = treeSize-1; i > 0; i--){
        pref[i] = max((ll)0, max(pref[i*2], sum[i*2]+pref[i*2+1]));
        suf[i] = max((ll)0, max(suf[i*2+1], sum[i*2+1] + suf[i*2]));
        sum[i] = sum[i*2] + sum[i*2+1];
        maxSum[i] = max((ll)0, max(maxSum[i*2], max(maxSum[i*2+1], suf[i*2]+pref[i*2+1])));
    }
}

ll qur(){
    return maxSum[1];
}
 
void update(ll val, ll a){
    ll va = a+treeSize;
    maxSum[va] = max((ll)0, val);
    sum[va] = val;
    pref[va] = max((ll)0, val);
    suf[va] = max((ll)0, val);
 
    va/=2;
    while(va>0){
//            cout<<va<<endl;
        pref[va] = max((ll)0, max(pref[va*2], sum[va*2]+pref[va*2+1]));
        suf[va] = max((ll)0, max(suf[va*2+1], sum[va*2+1] + suf[va*2]));
        sum[va] = sum[va*2] + sum[va*2+1];
        maxSum[va] = max((ll)0, max(maxSum[va*2], max(maxSum[va*2+1], suf[va*2]+pref[va*2+1])));
        va/=2;
    }
}
int main()
{
    ios_base::sync_with_stdio((ll)0); cin.tie(nullptr); cout.tie(nullptr);
    ll k;
    cin>>n>>k;
    buildTree();
    vector<ll> kol;
    for(ll i = 0; i < n; i++){
	kol.push_back(i);	
    }
    shuffle(kol.begin(), kol.end(), default_random_engine(rand()));
    vector<vector<ll>> tab(2, vector<ll>(n));
    vector<bool> wynik(n);
    for(ll i = 0; i < n; i++){
		ll a; cin>>a;
		tab[0][i] = a;
    }
    for(ll i = 0; i < n; i++){
		ll a; cin>>a;
		tab[1][i] = a;
    }
    for(ll i = 0; i < k; i++){
	    ll a = tab[0][kol[i]];
	    wynik[kol[i]] = 1;
        maxSum[kol[i]+treeSize] = max((ll)0, a);
        sum[kol[i]+treeSize] = a;
        pref[kol[i]+treeSize] = max((ll)0, a);
        suf[kol[i]+treeSize] = max((ll)0, a);
    }
    for(ll i = k; i < n; i++){
	    ll a = tab[1][kol[i]];
        maxSum[kol[i]+treeSize] = max((ll)0, a);
        sum[kol[i]+treeSize] = a;
        pref[kol[i]+treeSize] = max((ll)0, a);
        suf[kol[i]+treeSize] = max((ll)0, a);
    }
    buduj();
    vector<ll> rozw(n);
for(ll i = 0; i < n; i++) rozw[i] = wynik[i];
    ll best = qur();
    ll stala2 = 100;
    if(n>=400) stala2 = 10;
    if(k==n||k==0) {stala2=0;}//; stala2=0;}
    while(stala2--){
	    ll stala = 100000;
	    if(n>10000) stala = 100000;
	    shuffle(kol.begin(), kol.end(), default_random_engine(rand()));
    for(ll i = 0; i < k; i++){
	    ll a = tab[0][kol[i]];
	    wynik[kol[i]] = 1;
        maxSum[kol[i]+treeSize] = max((ll)0, a);
        sum[kol[i]+treeSize] = a;
        pref[kol[i]+treeSize] = max((ll)0, a);
        suf[kol[i]+treeSize] = max((ll)0, a);
    }
    for(ll i = k; i < n; i++){
	    ll a = tab[1][kol[i]];
	    wynik[kol[i]] = 0;
        maxSum[kol[i]+treeSize] = max((ll)0, a);
        sum[kol[i]+treeSize] = a;
        pref[kol[i]+treeSize] = max((ll)0, a);
        suf[kol[i]+treeSize] = max((ll)0, a);
    }
    buduj();
	    while(stala--){
		ll x1 = rand()%k;
		ll x2 = rand()%(n-k);	
		x2+=k;
		ll tmp = qur();
		update(tab[1][kol[x1]], kol[x1]);
		update(tab[0][kol[x2]], kol[x2]);
		if(qur()<tmp){
			wynik[kol[x1]] = false;
			wynik[kol[x2]] = true;
			swap(kol[x1], kol[x2]);
		}else {
			update(tab[0][kol[x1]], kol[x1]);
			update(tab[1][kol[x2]], kol[x2]);
		}
		if(qur()<best){
			best = qur();
			for(ll i = 0; i < n; i++) rozw[i] = wynik[i];
		}
	    }
    }
    cout<<best<<'\n';
    //return 0;
    for(auto it:rozw){
	    if(it) cout<<'A';
	    else cout<<'B';
    }
    cout<<'\n';
}