fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <algorithm>
  6. #include <bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. #define saleh                         \
  11.     ios_base::sync_with_stdio(false); \
  12.     cin.tie(nullptr);
  13. #define ll long long
  14. #define all(v) (v).begin(), (v).end()
  15.  
  16. const ll md = 1e9 + 7;
  17. vector<string> str[21];
  18. vector<ll> money(21);
  19. int main()
  20. {
  21.     saleh;
  22.     int ind = 0;
  23.     string line;
  24.     set<string> all_topics;
  25.     while (getline(cin, line))
  26.     {
  27.         stringstream ss(line);
  28.         int number;
  29.         ss >> number;
  30.         money[ind] = number;
  31.  
  32.         string word;
  33.         while (ss >> word)
  34.         {
  35.             str[ind].push_back(word);
  36.             all_topics.insert(word);
  37.         }
  38.         ind++;
  39.     }
  40.  
  41.     map<string, int> id;
  42.     int idd = 0;
  43.     for (auto a : all_topics)
  44.     {
  45.         id[a] = idd++;
  46.     }
  47.  
  48.     vector<ll> v(ind, 0);
  49.     for (int i = 0; i < ind; i++)
  50.     {
  51.         for (auto a : str[i])
  52.         {
  53.             v[i] |= (1 << id[a]);
  54.         }
  55.     }
  56.     vector<ll> dp((1 << idd), 1e10);
  57.  
  58.     for (int i = 0; i < ind; i++)
  59.     {   
  60.         dp[v[i]] = min(money[i] , dp[v[i]]);   
  61.  
  62.     }
  63.  
  64.     dp[0] = 0;
  65.     for (int j = 0; j < ind; j++)
  66.     {   
  67.         for (int i = 1; i < (1 << idd); i++)
  68.         {   
  69.             dp[i|v[j]] = min(dp[i|v[j]],dp[i]+money[j]);
  70.         }
  71.     }
  72.     cout<<dp[(1<<idd)-1];
  73.  
  74. }
  75.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
300 Backtracking Dynamic_Programming Greedy
125 Dynamic_Programming
35 Backtracking
85 Greedy
120 Backtracking Dynamic_Programming
80 Greedy Backtracking
stdout
copy 
200
https://ideone.com/mcTrml
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!