#include<bits/stdc++.h>
#include "molecules.h"
using namespace std;
vector<int> find_subset(int l, int r, vector<int>w){
int n = w.size();
vector<vector<long long>>table(n + 1, vector<long long>(n + 1, -1e15));
vector<vector<pair<int, int>>>par(n + 1, vector<pair<int, int>>(n + 1, {-1, -1}));
/// table[k][i] -> max_weight <= r we can get if we choose k weights from first i weights
/// table[k][i] = max(min(r, table[k - 1][i - 1] + w[i]), table[k][i - 1])
table[0][0] = 0;
for(int k = 1;k <= n;++k){
for(int i = 1;i <= n;++i){
table[0][i] = 0;
table[k][i] = table[k][i - 1];
par[k][i] = {k, i - 1};
long long tempo = table[k - 1][i - 1] + w[i - 1];
if(tempo <= r && table[k][i] < tempo){
table[k][i] = tempo;
par[k][i] = {k - 1, i - 1};
}
// cout << "table[" << k << "][" << i << "]=" << table[k][i] << ", {" << par[k][i].first << ", " << par[k][i].second << "}\n";
}
}
pair<int, int>num = {-1, -1};
for(int i = 1;i <= n;++i){
if(table[i][n] >= l){num = {i, n};break;}
}
vector<int>ans;
while(num.first > 0){
int k = num.first, i = num.second;
pair<int, int>tempo = {k - 1, i - 1};
if(par[k][i] == tempo){
ans.push_back(i - 1);
}
num = par[k][i];
}
return ans;
}
//int main()
//{
// int l, r, n;
// cin >> l >> r >> n;
// vector<int>v(n);
// for(int i = 0;i < n;++i)cin >> v[i];
// vector<int>ans = find_subset(l, r, v);
// for(int i : ans)cout << i << " ";
//}
