fork download
copy 
  1.  
  2.     #include <bits/stdc++.h>
  3.  
  4.     using namespace std;
  5.  
  6.     using ll = long long;
  7.     const int MOD = 1000000007; 
  8.     const int MOD2 =  998244353; 
  9.     const ll INF = 1e18;
  10.     const int MX = 1000001; //check the limits, dummy
  11.  
  12.  
  13.     ll modExp(ll base, ll power) {
  14.         if (power == 0) {
  15.             return 1;
  16.         } else {
  17.             ll cur = modExp(base, power / 2); cur = cur * cur; cur = cur % MOD;
  18.             if (power % 2 == 1) cur = cur * base;
  19.             cur = cur % MOD;
  20.             return cur;
  21.         }
  22.     }
  23.  
  24.     ll inv(ll base) {
  25.         return modExp(base, MOD-2);
  26.     }
  27.  
  28.  
  29.     ll mul(ll A, ll B) {
  30.         return (A*B)%MOD;
  31.     }
  32.  
  33.     ll add(ll A, ll B) {
  34.         return (A+B)%MOD;
  35.     }
  36.  
  37.     ll dvd(ll A, ll B) {
  38.         return mul(A, inv(B));
  39.     }
  40.  
  41.     ll sub(ll A, ll B) {
  42.         return (A-B+MOD)%MOD;
  43.     }
  44.     ll cielDiv(ll A , ll B) {
  45.         return (A + B - 1)/B;
  46.     } 
  47.  
  48.     ll* facs = new ll[MX];
  49.     ll* facInvs = new ll[MX];
  50.  
  51.     ll choose(ll a, ll b) {
  52.         if (b > a) return 0;
  53.         if (a < 0) return 0;
  54.         if (b < 0) return 0;
  55.         ll cur = facs[a];
  56.         cur = mul(cur, facInvs[b]);
  57.         cur = mul(cur, facInvs[a-b]);
  58.         return cur;
  59.     }
  60.  
  61.  
  62.  
  63.  
  64.     void initFacs() {
  65.         facs[0] = 1; 
  66.         facInvs[0] = 1;
  67.         for (int i = 1 ; i < MX ; i ++ ) {
  68.             facs[i] = (facs[i-1] * i) % MOD;
  69.             facInvs[i] = inv(facs[i]);
  70.         }
  71.     }
  72.  
  73.     int main()  {
  74.         ios_base::sync_with_stdio(0); cin.tie(0);  
  75.         ll n,m,k;
  76.         cin >> n >> m >> k;
  77.         vector<ll> a(n);
  78.         for (int i = 0 ; i <  n; i ++) {
  79.             cin >> a[i]; 
  80.         }
  81.  
  82.  
  83.         vector<vector<ll>> s(n,vector<ll> (n ,0));
  84.         vector<vector<ll>> dp(1 << n ,vector<ll> (n ,0));
  85.  
  86.         dp[0][0] = 0;
  87.  
  88.         for (int i = 0 ; i < k ; i++) {
  89.             ll a,b,c; cin >> a >> b; 
  90.             a -- ; b --; 
  91.  
  92.             s[a][b] += c; 
  93.         }
  94.  
  95.         ll res = -INF; 
  96.  
  97.         for (int i = 0 ; i < n; i ++ ) {
  98.             dp[1 << i][i] = a[i];
  99.         }
  100.         for (int  i =0 ; i < (1 << n) ; i ++) {
  101.             for (int prev = 0 ; prev < n; prev ++) {
  102.                 if (dp[i][prev] == -INF) continue; 
  103.                 int count = 0;
  104.                 for (int j = 0 ;j < n; j  ++) {
  105.                     if ((1 << j) & i) {
  106.                         count ++; 
  107.                     }
  108.                 }
  109.  
  110.                 if (count == m) {
  111.                     res = max(res,dp[i][prev]); 
  112.                     continue;
  113.                 }
  114.                 for (int j = 0 ;j < n; j  ++) {
  115.                     if (!((1 << j) & i)) {
  116.                         dp[i | (1 << j)][j] = max(dp[i | (1 << j)][j], dp[i][prev] + a[j] + s[prev][j]);
  117.                     }
  118.                 }
  119.             }
  120.         }
  121.         cout << res << endl; 
  122.  
  123.         return 0;
  124.     }
  125.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4 3 2
1 2 3 4
2 1 5
3 4 2
stdout
copy 
9
https://ideone.com/N8pMlw
language:
C++ (gcc 8.3)
created:
5 hours 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!