fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define dd double
  5. #define ld long double
  6. #define ull unsigned long long
  7. #define yes cout << "YES\n"
  8. #define no cout << "NO\n"
  9. #define el "\n"
  10. #define Arwa ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  11. #define fix(x) cout << fixed << setprecision(x)
  12. #define all(v) v.begin(),v.end()
  13. #define dpp(v,val) memset(v,val,sizeof(v))
  14. #define mod 1e9+7
  15. #define oo 1e9
  16. const int N = 1e5 + 5;
  17. int n,k;
  18. vector<int>taste,cal;
  19. int dp[N],dp2[N];
  20. int solve(int i,int t,int c) 
  21. {
  22.    if(i==n) 
  23.    {
  24.       if(c*k-t==0&&t!=0) return t;
  25.       return 0;
  26.    }
  27.    int ret;
  28.    if(t>k*c) ret=dp[abs(k*c-t)];
  29.    else ret=dp2[(k*c-t)+10000];
  30.    if(ret!=-1) return ret;
  31.    int tk=0,l=0;
  32.    tk=solve(i+1,t+taste[i],c+cal[i]);
  33.    l=solve(i+1,t,c);
  34.    return ret=max(tk,l);
  35. }
  36. void HereWeGoAgain()
  37. {
  38.   cin>>n>>k;
  39.   taste.resize(n); cal.resize(n);
  40.   for(int i=0;i<n;i++)
  41.   cin>>taste[i];
  42.   for(int i=0;i<n;i++)
  43.   cin>>cal[i];
  44.    dpp(dp,-1);dpp(dp2,-1);
  45.   if(solve(0,0,0)==0)cout<<-1<<el;
  46.   else cout<<solve(0,0,0);
  47. }
  48. int32_t main() 
  49. {
  50.     Arwa
  51.     int t=1;
  52.     //cin>>t;
  53.     for(int i=1;i<=t;i++)
  54.     {
  55.     HereWeGoAgain();
  56.     }
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/G3ICd4
language:
C++ (gcc 8.3)
created:
4 days 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!