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
// 2021-3-wys-wystawa-brut.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>

constexpr int MAXN = 1e5 + 7;
constexpr long long INF = ((long long)(1e9)) * ((long long)(1e8));

long long ta[MAXN];
long long tb[MAXN];

int k, n;

long long currsm;
long long mnsm;
bool istkn[MAXN];
bool mntkn[MAXN];
int i, j;

void hndl(long long currmn, long long currmxpref)
{
	if (j > k)
	{
		return;
	}
	if (j + n - i < k)
	{
		return;
	}
	if (i == n && currmxpref < mnsm)
	{
		if (j != k)
		{
			return;
		}
		mnsm = currmxpref;
		for (size_t i = 0; i < n; i++)
		{
			mntkn[i] = istkn[i];
		}
		return;
	}

	currsm += ta[i];
	istkn[i] = true;
	j++;
	i++;
	hndl(std::min(currmn, currsm), std::max(currmxpref, currsm - currmn));
	i--;
	j--;
	istkn[i] = false;
	currsm -= ta[i];

	currsm += tb[i];
	i++;
	hndl(std::min(currmn, currsm), std::max(currmxpref, currsm - currmn));
	i--;
	currsm -= tb[i];
}

int main()
{
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> n >> k;
	for (size_t i = 0; i < n; i++)
	{
		std::cin >> ta[i];
	}
	for (size_t i = 0; i < n; i++)
	{
		std::cin >> tb[i];
	}
	i = 0;
	j = 0;
	mnsm = INF;
	hndl(0, 0);
	std::cout << mnsm << '\n';
	for (size_t i = 0; i < n; i++)
	{
		std::cout << (mntkn[i] ? 'A' : 'B');
	}
	std::cout << '\n';
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file