#include <bits/stdc++.h>
using namespace std;
typedef bitset<128> bits_t;
void lue_syote(vector<int>& hinnat, unordered_map<bits_t, int>& palkkiot) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
hinnat.resize(n);
for (int i = 0; i < n; ++i) {
cin >> hinnat[i];
}
palkkiot.clear();
for (int i = 0; i < m; ++i) {
bits_t yhdistelmä;
int k, x;
cin >> k >> x;
for (int j = 0; j < k; ++j) {
int indeksi;
cin >> indeksi;
indeksi -= 1;
yhdistelmä.set(indeksi);
}
palkkiot[yhdistelmä] += x;
}
}
void luo_syote(vector<int>& hinnat, unordered_map<bits_t, int>& palkkiot, int seed) {
srand(seed);
int n = 20, m = n + rand() % 20 + 1;
hinnat.resize(n);
for (int i = 0; i < n; ++i) {
hinnat[i] = rand() % 1000 + 1;
}
palkkiot.clear();
for (int i = 0; i < m; ++i) {
bits_t yhdistelmä;
int k = rand() % n + 1;
for (int j = 0; j < k; ++j) {
int indeksi = rand() % n;
yhdistelmä.set(indeksi);
}
int x = rand() % 1000 + 1;
palkkiot[yhdistelmä] += x;
}
}
void ratkaise(vector<int> hinnat, unordered_map<bits_t, int> palkkiot, bool testi) {
int n = hinnat.size();
for (int i = 0; i < n; ++i) {
int paras_arvo = -hinnat[i];
for (const auto& [yhdistelmä, palkkio] : palkkiot) {
if (yhdistelmä.test(i)) {
paras_arvo += palkkio;
}
}
if (paras_arvo <= 0) {
unordered_set<bits_t> poistettavat;
for (const auto& [yhdistelmä, palkkio] : palkkiot) {
if (yhdistelmä.test(i)) {
poistettavat.insert(yhdistelmä);
}
}
for (const auto& yhdistelmä : poistettavat) {
palkkiot.erase(yhdistelmä);
}
}
}
int d = 0;
for (const auto& [yhdistelmä, _] : palkkiot) {
d = max(d, (int) yhdistelmä.count());
}
auto laske_arvo = [&](bits_t yhdistelmä) {
int arvo = 0;
for (int i = 0; i < n; ++i) {
if (yhdistelmä.test(i)) {
arvo -= hinnat[i];
}
}
for (const auto& [palkkio_yhdistelmä, palkkio] : palkkiot) {
if ((yhdistelmä & palkkio_yhdistelmä) == palkkio_yhdistelmä) {
arvo += palkkio;
}
}
return arvo;
};
auto laske_max_arvo = [&](bits_t yhdistelmä, bits_t ohitetut) {
int arvo = 0;
for (int i = 0; i < n; ++i) {
if (yhdistelmä.test(i)) {
arvo -= hinnat[i];
}
}
for (const auto& [palkkio_yhdistelmä, palkkio] : palkkiot) {
if ((ohitetut & palkkio_yhdistelmä) == bits_t(0)) {
arvo += palkkio;
}
}
return arvo;
};
auto ilmoita_tulos = [&](bits_t yhdistelmä) {
cout << laske_arvo(yhdistelmä) << "\n";
cout << yhdistelmä.count() << "\n";
for (int i = 0; i < n; ++i) {
if (yhdistelmä.test(i)) {
cout << (i + 1) << " ";
}
}
cout << endl;
};
bits_t selvästi_kannattavat;
int selvästi_kannattavat_arvo = 0;
for (int i = 0; i < n; ++i) {
bool muutos = false;
for (const auto& [yhdistelmä, palkkio] : palkkiot) {
bits_t uusi = selvästi_kannattavat | yhdistelmä;
if (uusi == selvästi_kannattavat) {
continue;
}
int uusi_arvo = laske_arvo(uusi);
if (uusi_arvo >= selvästi_kannattavat_arvo) {
muutos = true;
selvästi_kannattavat = uusi;
selvästi_kannattavat_arvo = uusi_arvo;
}
}
if (!muutos) {
break;
}
}
auto pieni_tapaus = [&]() {
bits_t paras_yhdistelmä = 0;
int paras_arvo = 0;
for (uint32_t yhdistelmä = 0; yhdistelmä < (uint32_t(1) << n); ++yhdistelmä) {
bits_t bs_yhdistelmä(yhdistelmä);
int arvo = laske_arvo(bs_yhdistelmä);
if (arvo > paras_arvo) {
paras_yhdistelmä = bs_yhdistelmä;
paras_arvo = arvo;
}
}
return paras_yhdistelmä;
};
auto heuristiikka = [&]() {
map<int, bits_t> tilanteet;
tilanteet[selvästi_kannattavat_arvo] = selvästi_kannattavat;
for (const auto& [yhdistelmä, _] : palkkiot) {
map<int, bits_t> uudet_tilanteet;
for (auto [_, edellinen]: tilanteet) {
bits_t uusi = edellinen | yhdistelmä;
if (uusi != edellinen) {
int uusi_arvo = laske_arvo(uusi);
tilanteet[uusi_arvo] = uusi;
if (uusi_arvo >= selvästi_kannattavat_arvo) {
selvästi_kannattavat = uusi;
selvästi_kannattavat_arvo = uusi_arvo;
}
}
}
while (tilanteet.size() > 13000) {
tilanteet.erase(tilanteet.begin());
}
}
return selvästi_kannattavat;
};
auto haku = [&]() {
struct tila_t {
bits_t yhdistelmä, ohitetut;
int i;
int arvo, max_arvo;
bool operator<(const tila_t& other) const {
if (max_arvo != other.max_arvo) {
return max_arvo < other.max_arvo;
}
return arvo < other.arvo;
}
};
auto tee_tila = [&](bits_t yhdistelmä, bits_t ohitetut, int i) {
tila_t tila {yhdistelmä, ohitetut, i};
tila.arvo = laske_arvo(yhdistelmä);
tila.max_arvo = laske_max_arvo(yhdistelmä, ohitetut);
return tila;
};
priority_queue<tila_t> pq;
bits_t paras_yhdistelmä;
int paras_arvo = -1;
auto lisää_tila = [&](bits_t yhdistelmä, bits_t ohitetut, int i) {
tila_t t = tee_tila(yhdistelmä, ohitetut, i);
if (t.max_arvo < paras_arvo) {
return;
}
if (t.arvo > paras_arvo) {
paras_yhdistelmä = t.yhdistelmä;
paras_arvo = t.arvo;
}
pq.push(t);
};
lisää_tila(selvästi_kannattavat, 0, 0);
while (!pq.empty()) {
tila_t t = pq.top();
pq.pop();
if (t.max_arvo < paras_arvo) {
return;
}
while (t.i < n && (t.ohitetut.test(t.i) || t.yhdistelmä.test(t.i))) {
t.i += 1;
}
if (t.i == n) {
continue;
}
bits_t uusi_ohitetut = t.ohitetut;
lisää_tila(t.yhdistelmä, uusi_ohitetut.set(t.i), t.i + 1);
bits_t uusi_yhdistelmä = t.yhdistelmä;
lisää_tila(uusi_yhdistelmä.set(t.i), t.ohitetut, t.i + 1);
}
return paras_yhdistelmä;
};
bits_t paras_yhdistelmä;
if (testi) {
bits_t oikea_yhdistelmä = pieni_tapaus();
paras_yhdistelmä = haku();
if (paras_yhdistelmä != oikea_yhdistelmä) {
ilmoita_tulos(oikea_yhdistelmä);
cout << "----\n";
ilmoita_tulos(paras_yhdistelmä);
throw runtime_error("VIRHE");
}
return;
} else if (d == 1) {
paras_yhdistelmä = selvästi_kannattavat;
} else if (n <= 20) {
paras_yhdistelmä = pieni_tapaus();
} else {
paras_yhdistelmä = haku();
}
ilmoita_tulos(paras_yhdistelmä);
}
int main(int argc, char** argv) {
vector<int> hinnat;
unordered_map<bits_t, int> palkkiot;
if (argc == 2 && string(argv[1]) == "kotitesti") {
try {
lue_syote(hinnat, palkkiot);
ratkaise(hinnat, palkkiot, true);
for (int seed = 1; seed <= 1000; ++seed) {
cerr << "Testi " << seed << "\n";
luo_syote(hinnat, palkkiot, seed);
ratkaise(hinnat, palkkiot, true);
}
} catch (runtime_error& e) {
cerr << e.what() << "\n";
}
} else {
lue_syote(hinnat, palkkiot);
ratkaise(hinnat, palkkiot, false);
}
}
