#include "partition.h"
#include <iostream>
using namespace std;
#include <map>
#include <queue>

long long dp[2002][2002];
int lst[2002][2002];
pair<long long, int> v[2002];
bool used[2002];

std::vector<int> solve(std::vector<int> A) {
	int n = A.size();
	for (int i = 0; i < n; i++) {
		used[i] = 0;
		for (int j = 0; j <= n; j++) {
			dp[i][j] = 0;
			lst[i][j] = -1;
		}
	}
	for (int i = 0; i < n; i++) {
		v[i] = { A[i], i };
	}
	sort(v, v + n);
	dp[0][0] = 0;
	dp[0][1] = v[0].first;
	lst[0][1] = v[0].second;
	long long sum = 0;
	for (auto i : A) {
		sum += i;
	}
	sum = (sum + 1) / 2;
	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= n; j++) {
			dp[i][j] = dp[i - 1][j];
			if (j > 0 && dp[i - 1][j - 1] < sum && dp[i][j] < dp[i - 1][j - 1] + v[i].first) dp[i][j] = dp[i - 1][j - 1] + v[i].first, lst[i][j] = v[i].second;
		}
	}
	int j = 0, mn = n + 10;
	for (int i = 0; i <= n; i++) {
		if (dp[n - 1][i] >= sum) {
			if (mn > abs(i - ((int)n - i))) {
				mn = abs(i - ((int)n - i));
				j = i;
			}
		}
	}
	vector<int> res;
	int i = n - 1;
	while (i >= 0 && j >= 0) {
		if (lst[i][j] == -1) {
			i--;
		}
		else {
			used[lst[i][j]] = 1;
			res.push_back(lst[i][j]);
			i--, j--;
		}
	}
	reverse(res.begin(), res.end());
	for (int i = 0; i < A.size(); i++) {
		if (!used[i]) {
			res.push_back(i);
		}
	}
	return res;
}
