fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int 
  3. #define X first
  4. #define Y second
  5. using namespace std;
  6. ll dp[1005][15];
  7. ll N,M,c0,d0;
  8. ll a[15],b[15],c[15],d[15];
  9. ll dpf(ll n,ll m)
  10. {
  11.     if(n==0)return 0;
  12.     if(m==0)
  13.         return (n/c0)*d0;
  14.  
  15.     if(dp[n][m]!=-1)
  16.         return dp[n][m];
  17.     ll ans=dpf(n,m-1);
  18.     for(ll i=1;n-i*c0>=0;i++)
  19.         ans=max(ans,i*d0+dpf(n-i*c0,m-1));
  20.  
  21.     for(ll i=1;a[m]-i*b[m]>=0 && n-i*c[m]>=0 ;i++)
  22.         ans=max(ans,i*d[m]+dpf(n-i*c[m],m-1));
  23.     return dp[n][m]=ans;
  24. }
  25. int main()
  26. {
  27.     cin>>N>>M>>c0>>d0;
  28.     for(int i=1;i<=M;i++)
  29.         cin>>a[i]>>b[i]>>c[i]>>d[i];
  30.  
  31.     memset(dp,-1,sizeof(dp));
  32.     ll ans=dpf(N,M);
  33.     cout<<ans<<endl;
  34.  
  35.     return 0;
  36. }
Success #stdin #stdout 0s 4460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/8tnkFy
language:
C++14 (gcc 8.3)
created:
7 years 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!