#include #include #include #include using namespace std; #define in cin #define out cout int N, S; vector P; vector use; vector P2; vector P3; void print() { const char *space = ""; for (int i = 0; i < N; i++) { if (use[i]) { out << space << (i + 1); space = " "; } } out << endl; } void resolve(int k, int money) { //cout << "##" << k << " " << money << endl; if (money >= P[k]) { use[k] = 1; if (money == P[k]) { print(); } else if (k + 1 < N) { resolve(k + 1, money - P[k]); } } if (money >= 0) { use[k] = 0; if (k + 1 < N && money <= P2[k + 1] && money >= P3[k + 1]) { resolve(k + 1, money); } } } int main() { #if 0 P.push_back(1760539); P.push_back(7418905); P.push_back(7934794); P.push_back(9096288); P.push_back(9830269); P.push_back(832919); P.push_back(3394144); P.push_back(7553814); P.push_back(3143360); P.push_back(4632212); P.push_back(8133005); P.push_back(6416092); P.push_back(8390530); P.push_back(5917577); P.push_back(7629132); P.push_back(3124061); P.push_back(5028257); P.push_back(6906852); P.push_back(1608676); P.push_back(6133542); P.push_back(6688847); P.push_back(7117247); P.push_back(9324786); P.push_back(6773955); P.push_back(4024858); P.push_back(8153998); P.push_back(692743); P.push_back(8742190); P.push_back(5266294); P.push_back(2991635); P.push_back(248465); N = P.size(); S = 75354705; #else in >> N >> S; P.resize(N); for (int i = 0; i < N; i++) in >> P[i]; #endif use.resize(N); P2.resize(N); P2[N - 1] = P[N - 1]; for (int i = N - 2; i >= 0; i--) { P2[i] = P2[i + 1] + P[i]; } P3.resize(N); P3[N - 1] = P[N - 1]; for (int i = N - 2; i >= 0; i--) { P3[i] = min(P3[i + 1], P[i]); } resolve(0, S); }