Advertisement
Josif_tepe

Untitled

Jun 6th, 2022
876
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <set>
  4. #include <vector>
  5. #include <map>
  6. #include <fstream>
  7. #include <set>
  8. #include <cmath>
  9. using namespace std;
  10. long long memo[1 << 18];
  11. int n,m,k;
  12. map<int,pair<int,long long>> mp;
  13. int a[20];
  14. long long dp(int mask){
  15.     if(__builtin_popcount(mask) == m){
  16.         return 0;
  17.     }
  18.     if(memo[mask] != -1){
  19. //        return memo[mask];
  20.     }
  21.     long long res =0;
  22.     for (int i = 0; i < n; i++) {
  23.         if(mask & (1 << i)){
  24.             continue;
  25.         }
  26.         else{
  27.             int temp_mask = (mask | (1 << i));
  28.             pair<int,int> pir = mp[i];
  29.             if(mask & (1 << pir.first)){
  30.                 res= max(res,dp(temp_mask) + pir.second + a[i]);
  31.             }
  32.             else{
  33.                 res= max(res,dp(temp_mask) + a[i]);
  34.             }
  35.         }
  36.  
  37.     }
  38.     return memo[mask] = res;
  39. }
  40. int main(){
  41.     cin >> n >> m >> k;
  42.  
  43.     for (int i = 0; i < n; i++) {
  44.         cin >> a[i];
  45.     }
  46.  
  47.     for (int i = 0; i < k; i++) {
  48.         int x,y,z;
  49.         cin >> x >> y >> z;
  50.         x--;
  51.         y--;
  52.         mp[y] = make_pair(x,z);
  53.     }
  54.  
  55.     memset(memo,-1,sizeof memo);
  56.     cout << dp(0);
  57. }
  58.  
Advertisement
RAW Paste Data Copied
Advertisement