Problem: Example

Input

4 2 58 100
10 10 50 80


Output

75
2 3

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <map>
#include <tuple>
#include <iostream>
#include <deque>
#include <array>
#include <set>
#include <functional>
#include <memory>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
void set_if_renew(int& current_diff, int& current_t, int &current_cards, const int t, const int cards) {
	if (current_diff < std::abs(t - cards)) {
		current_diff = std::abs(t - cards);
		current_t = t;
		current_cards = cards;
	}
	else if (current_diff == std::abs(t - cards) && current_t > t) {
		current_t = t;
		current_cards = cards;
	}
}
struct Card {
	int value, index;
};
int main() {
	int n, k, a, b; std::cin >> n >> k >> a >> b;
	std::vector<Card> cards(n);
	for (auto i = 0; i < n; ++i) {
		std::cin >> cards[i].value;
		cards[i].index = i;
	}
	const int sum = std::accumulate(cards.begin(), cards.end(), 0, [](const int acc, const Card& c) {return acc + c.value; });
	const int max = std::max_element(cards.begin(), cards.end(), [](const Card &a, const Card &b) {return a.value < b.value; })->value;
	std::sort(cards.begin(), cards.end(), [](const Card& a, const Card& b) {return a.value < b.value; });
	std::vector<std::vector<int>> last_index;
	for (auto i = 0; i <= k; ++i) {last_index.emplace_back(std::max(b, max * i) + 1, INT_MAX);}
	std::queue<int> queue; queue.push(0); last_index[0][0] = 0;
	for (auto count = 1; count <= k; ++count) {
		for (int _c = queue.size(); _c > 0; --_c) {
			auto top = queue.front(); queue.pop();
			for (auto i = last_index[count - 1][top]; i < n && cards[i].value + top < last_index[count].size(); ++i) {
				if (last_index[count][cards[i].value + top] == INT_MAX) {
					queue.push(cards[i].value + top);
				}
				if (last_index[count][cards[i].value + top] > i) {
					last_index[count][cards[i].value + top] = i + 1;
				}
			}
		}
	}
	std::vector<int> suspects;
	while (!queue.empty()) {
		suspects.push_back(queue.front()); queue.pop();
	}
	std::sort(suspects.begin(), suspects.end());
	int max_diff = -1;
	int min_t = INT_MAX;
	int min_cards = 0;
	for (int i = std::lower_bound(suspects.begin(), suspects.end(), a) - suspects.begin(); i < suspects.size(); ++i) {
		if (i == 0) {
			max_diff = suspects[0] - a;
			min_t = a;
			min_cards = suspects[0];
		}
		else {
			if (suspects[i - 1] >= b) break;
			int upper = suspects[i];
			int lower = suspects[i - 1];
			int diff = upper - lower;
			if (max_diff < diff / 2) {
				if (lower <= a && a <= upper) {
					if (a - lower < upper - a) set_if_renew(max_diff, min_t, min_cards, a, lower);
					else set_if_renew(max_diff, min_t, min_cards, a, upper);
				}
				if (lower <= b && b <= upper) {
					if (b - lower < upper - b) set_if_renew(max_diff, min_t, min_cards, b, lower);
					else set_if_renew(max_diff, min_t, min_cards, b, upper);
				}
				if (a <= lower + diff / 2 && lower + diff / 2 <= b) {
					set_if_renew(max_diff, min_t, min_cards, lower + diff / 2, lower);
				}
				if (a <= upper - diff / 2 && upper - diff / 2 <= b) {
					set_if_renew(max_diff, min_t, min_cards, upper - diff / 2, upper);
				}
			}
		}
	}
	if (suspects.back() <= b) set_if_renew(max_diff, min_t, min_cards, b, suspects.back());
	std::cout << min_t << "\n";
	std::vector<int> result;
	for (int i = k; i > 0; --i) {
		result.push_back(cards[last_index[i][min_cards] - 1].index + 1);
		min_cards = min_cards - cards[last_index[i][min_cards] - 1].value;
	}
	for (auto i = 0; i < result.size(); ++i) {
		if (i != 0) std::cout << ' ';
		std::cout << result[i];
	}
	std::cout << '\n';
}