Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cstring>
- using namespace std;
- int n, m, k;
- struct vraboten {
- int plata, br_predmeti;
- vector<int> predmet;
- };
- int dp[202][1 << 8][1 << 8];
- vraboten vraboteni[100], kandidati[220];
- int rec(int at, int p1, int p2) {
- if(__builtin_popcount(p1) == n and __builtin_popcount(p2) == n) {
- return 0;
- }
- if(at == k) {
- return 1e9;
- }
- if(dp[at][p1][p2] != -1) {
- return dp[at][p1][p2];
- }
- int result = 1e9;
- int t1 = p1, t2 = p2;
- for(int i = 0; i < kandidati[at].br_predmeti; i++) {
- int x = kandidati[at].predmet[i];
- if(t1 & (1 << x)) {
- t2 |= (1 << x);
- }
- else {
- t1 |= (1 << x);
- }
- }
- result = min(result, rec(at + 1, t1, t2) + kandidati[at].plata);
- result = min(result, rec(at + 1, p1, p2));
- return dp[at][p1][p2] = result;
- }
- int main() {
- cin >> n >> m;
- int p1 = 0, p2 = 0;
- int suma_plata = 0;
- for(int i = 0; i < m; i++) {
- cin >> vraboteni[i].plata >> vraboteni[i].br_predmeti;
- suma_plata += vraboteni[i].plata;
- for(int j = 0; j < vraboteni[i].br_predmeti; j++) {
- int x;
- cin >> x;
- x--;
- vraboteni[i].predmet.push_back(x);
- if(p1 & (1 << x)) {
- p2 |= (1 << x);
- }
- else {
- p1 |= (1 << x);
- }
- }
- }
- cin >> k;
- for(int i = 0; i < k; i++) {
- cin >> kandidati[i].plata >> kandidati[i].br_predmeti;
- for(int j = 0; j < kandidati[i].br_predmeti; j++) {
- int x;
- cin >> x;
- x--;
- kandidati[i].predmet.push_back(x);
- }
- }
- memset(dp, -1, sizeof dp);
- cout << rec(0, p1, p2) + suma_plata << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement