4eyes4u

Untitled

Mar 14th, 2016
171
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.86 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define f first
  3. #define s second
  4. using namespace std;
  5.  
  6. const int N=110;
  7.  
  8. int a[N], b[N], n, k, sum, state;
  9. map<int, int> dp;
  10. vector<pair<int, int> > v;
  11.  
  12. int main()
  13. {
  14.     scanf ("%d%d", &n, &k);
  15.  
  16.     for (int i=1;i<=n;i++) scanf ("%d", &a[i]);
  17.     for (int i=1;i<=n;i++) scanf ("%d", &b[i]), b[i]*=k;
  18.  
  19.     for (int i=1;i<=n;i++)
  20.     {
  21.         v.clear();
  22.         for (map<int, int>::iterator it=dp.begin();it!=dp.end();it++)
  23.         {
  24.             sum=it->f;
  25.             state=it->s;
  26.             if (dp[sum+a[i]-b[i]]==0) v.push_back(make_pair(sum+a[i]-b[i], state+a[i]));
  27.             else dp[sum+a[i]-b[i]]=max(dp[sum+a[i]-b[i]], state+a[i]);
  28.         }
  29.         for (int j=0;j<v.size();j++) dp[v[j].f]=max(dp[v[j].f], v[j].s);
  30.         dp[a[i]-b[i]]=max(dp[a[i]-b[i]], a[i]);
  31.     }
  32.  
  33.     printf ("%d", dp[0]);
  34.  
  35.     return 0;
  36. }
Advertisement
Add Comment
Please, Sign In to add comment