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 n, k, a[N], x[N], sum, state;
- map<int, int> dp, check;
- vector<pair<int, int> > v; //za nove sume, prvo prolazim kroz mapu pa tek onda njih dodajem da ne pokvarim it!=dp.end
- 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", &x[i]);
- x[i]*=-k;
- x[i]+=a[i];
- }
- 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 (check[sum+x[i]]) dp[sum+x[i]]=max(dp[sum+x[i]], state+a[i]);
- else v.push_back(make_pair(sum+x[i], state+a[i]));
- }
- for (int j=0;j<v.size();j++)
- {
- check[v[j].f]=true;
- dp[v[j].f]=max(dp[v[j].f], v[j].s);
- }
- dp[x[i]]=max(dp[x[i]], a[i]);
- check[x[i]]=true;
- }
- if (check[0]) printf ("%d", dp[0]);
- else printf ("-1");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment