fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned ll
  4. #define ld long double
  5. #define int long long
  6. #define pb push_back
  7. #define f first
  8. #define s second
  9. #define pq priority_queue
  10. #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  11. #define read_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  12.  
  13. using namespace std;
  14.  
  15. // #include <ext/pb_ds/assoc_container.hpp>
  16. // #include <ext/pb_ds/tree_policy.hpp>
  17. // using namespace __gnu_pbds;
  18.  
  19. // template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  20.  
  21. void solve(){
  22.     int n, m, d, f; cin>>n>>m>>d>>f;
  23.  
  24.     int a[n+m];
  25.     for(int i=0; i<n; i++) cin>>a[i];
  26.     for(int i=0; i<m; i++) cin>>a[i+n];
  27.  
  28.     vector<tuple<int, int, int>> cp(d);
  29.     for(int i=0; i<d; i++){
  30.         int cut, perc, mxi; cin>>cut>>perc>>mxi;
  31.         cp[i]={cut, perc, mxi};
  32.     }
  33.  
  34.  
  35.     int len=n+m; int len2=1ll<<(n+m);
  36.     int sm[len2]{}, cst[len2]{};
  37.     vector<int> dp(len2, 1e18); dp[0]=0;
  38.     for(int i=0; i<len2; i++){
  39.         for(int j=0; j<len; j++){
  40.             if(i&(1ll<<j)) sm[i]+=a[j];
  41.         }
  42.         cst[i]=f+sm[i];
  43.         for(auto [cut, perc, mxi]:cp){
  44.             if(cut>sm[i]) continue;
  45.             int loss=((100-perc)*sm[i])/100;
  46.             loss=min(loss, mxi);
  47.             cst[i]=min(cst[i], f+sm[i]-loss);
  48.         }
  49.     }
  50.     for(int i=0; i<(1ll<<m); i++){
  51.         dp[i<<n]=0;
  52.     }
  53.  
  54.  
  55.     for(int i=1; i<len2; i++){
  56.         for(int j=i; j; j=(j-1)&i){ // taking out
  57.             dp[i]=min(dp[i], cst[j]+dp[i^j]);
  58.         }
  59.     }
  60.  
  61.     int ans=dp[len2-1];
  62.     for(int i=0; i<(1ll<<m); i++){
  63.         ans=min(ans, dp[(1ll<<n)-1+(i<<n)]);
  64.     }
  65.     cout<<ans<<endl;
  66. }
  67.  
  68. int32_t main() {
  69.     fast;
  70.  
  71.     int t; 
  72.     t=1;
  73.     // cin>>t;
  74.     while(t--){
  75.         solve();
  76.     }
  77.     return 0;
  78. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/OUHnif
language:
C++14 (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!