Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define f first
- #define s second
- using namespace std;
- const int N=110;
- int a[N], b[N], n, k, sum, state;
- map<int, int> dp;
- vector<pair<int, int> > v;
- int main()
- {
- scanf ("%d%d", &n, &k);
- for (int i=1;i<=n;i++) scanf ("%d", &a[i]);
- for (int i=1;i<=n;i++) scanf ("%d", &b[i]), b[i]*=k;
- for (int i=1;i<=n;i++)
- {
- v.clear();
- for (map<int, int>::iterator it=dp.begin();it!=dp.end();it++)
- {
- sum=it->f;
- state=it->s;
- if (dp[sum+a[i]-b[i]]==0) v.push_back(make_pair(sum+a[i]-b[i], state+a[i]));
- else dp[sum+a[i]-b[i]]=max(dp[sum+a[i]-b[i]], state+a[i]);
- }
- for (int j=0;j<v.size();j++) dp[v[j].f]=max(dp[v[j].f], v[j].s);
- dp[a[i]-b[i]]=max(dp[a[i]-b[i]], a[i]);
- }
- printf ("%d", dp[0]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment