4eyes4u

Untitled

Mar 14th, 2016
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.11 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 n, k, a[N], x[N], sum, state;
  9. map<int, int> dp, check;
  10. vector<pair<int, int> > v; //za nove sume, prvo prolazim kroz mapu pa tek onda njih dodajem da ne pokvarim it!=dp.end
  11.  
  12. int main()
  13. {
  14.     scanf ("%d%d", &n, &k);
  15.     for (int i=1;i<=n;i++) scanf ("%d", &a[i]);
  16.     for (int i=1;i<=n;i++)
  17.     {
  18.         scanf ("%d", &x[i]);
  19.         x[i]*=-k;
  20.         x[i]+=a[i];
  21.     }
  22.  
  23.     for (int i=1;i<=n;i++)
  24.     {
  25.         v.clear();
  26.         for (map<int, int>::iterator it=dp.begin();it!=dp.end();it++)
  27.         {
  28.             sum=it->f;
  29.             state=it->s;
  30.             if (check[sum+x[i]]) dp[sum+x[i]]=max(dp[sum+x[i]], state+a[i]);
  31.             else v.push_back(make_pair(sum+x[i], state+a[i]));
  32.         }
  33.         for (int j=0;j<v.size();j++)
  34.         {
  35.             check[v[j].f]=true;
  36.             dp[v[j].f]=max(dp[v[j].f], v[j].s);
  37.         }
  38.         dp[x[i]]=max(dp[x[i]], a[i]);
  39.         check[x[i]]=true;
  40.     }
  41.  
  42.     if (check[0]) printf ("%d", dp[0]);
  43.     else printf ("-1");
  44.  
  45.     return 0;
  46. }
Advertisement
Add Comment
Please, Sign In to add comment