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
#include "bits/stdc++.h" // Tomasz Nowak
using namespace std;     // University of Warsaw
using LL = long long;
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
#define ssize(x) int(x.size())
template<class A, class B> auto& operator<<(ostream &o, pair<A, B> p) {
	return o << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &o, T x) -> decltype(x.end(), o) {
	o << '{'; int i = 0; for(auto e : x) o << (", ")+2*!i++ << e; return o << '}';
}
#ifdef DEBUG
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n'
#else
#define debug(...) {}
#endif

LL psoms(vector<int> v) {
	LL ret = 0, best = 0;
	for(int x : v) {
		best = max(best + x, 0LL);
		ret = max(ret, best);
	}
	return ret;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for(int &ai : a)
		cin >> ai;
	vector<int> b(n);
	for(int &bi : b)
		cin >> bi;
	debug(n, k, a, b);

	auto get_dp = [&](LL m) {
		vector<LL> curr_dp(n + 1, m + 1), prev_dp(n + 1, m + 1);
		curr_dp[0] = 0;
		vector<vector<bool>> took_a(n + 1, vector<bool>(n + 1));
		FOR(i, 1, n) {
			prev_dp = curr_dp;
			fill(curr_dp.begin(), curr_dp.end(), m + 1);
			FOR(cnt_a, 0, n) {
				if(prev_dp[cnt_a] <= m and prev_dp[cnt_a] + b[i - 1] < curr_dp[cnt_a]) {
					curr_dp[cnt_a] = max(prev_dp[cnt_a] + b[i - 1], 0LL);
					// took_a[cnt_a] = false;
				}
				if(cnt_a > 0 and prev_dp[cnt_a - 1] <= m and prev_dp[cnt_a - 1] + a[i - 1] < curr_dp[cnt_a]) {
					curr_dp[cnt_a] = max(prev_dp[cnt_a - 1] + a[i - 1], 0LL);
					took_a[i][cnt_a] = true;
				}
			}
		}
		debug(m, curr_dp);
		return pair(curr_dp[k] <= m, took_a);
	};
	auto is_answer_leq = [&](LL m) {
		return get_dp(m).first;
	};

	LL l = 0, r = 0;
	REP(i, n)
		r += max(0, max(a[i], b[i]));
	debug(l, r);
	r = max(r, 0LL);

	while(l != r) {
		LL m = (l + r) / 2;
		debug(l, m, r);
		if(is_answer_leq(m))
			r = m;
		else
			l = m + 1;
	}
	debug(l);

	cout << l << '\n';

	auto bool_table = get_dp(l).second;
	int i = n, rem_a = k;
	vector<bool> taking_a(n);
	while(i > 0) {
		taking_a[i - 1] = bool_table[i][rem_a];
		rem_a -= taking_a[--i];
	}
	debug(taking_a);

	vector<int> v(n);
	REP(j, n)
		v[j] = (taking_a[j] ? a[j] : b[j]);
	debug(v);
	assert(psoms(v) == l);

	REP(i, n)
		cout << (taking_a[i] ? 'A' : 'B');
	cout << '\n';
}