Advertisement
Josif_tepe

Untitled

Apr 20th, 2022
805
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstring>
  3.  
  4. using namespace std;
  5.  
  6. int a,n,k;
  7. int x[100];
  8. int dp[1005][1005];
  9.  
  10. int f(int idx, int at)
  11. {
  12.     if(idx==k)
  13.     {
  14.         return at;
  15.     }
  16.  
  17.     if(dp[idx][at]!=-1)
  18.     {
  19.         return dp[idx][at];
  20.     }
  21.     int rez=-1e9;
  22.     if(at-x[idx]>=0)
  23.     {
  24.         rez=max(rez, f(idx+1, at-x[idx]));
  25.     }
  26.     if(at+x[idx]<=n)
  27.     {
  28.         rez=max(rez, f(idx+1, at+x[idx]));
  29.     }
  30.     return dp[idx][at]=rez;
  31. }
  32.  
  33. int main()
  34. {
  35.     cin>>a>>n;
  36.     cin>>k;
  37.     memset(dp,-1,sizeof dp);
  38.     for(int i=0;i<k;i++)
  39.     {
  40.         cin>>x[i];
  41.     }
  42.     if(f(0, a) < 0) cout << -1<<endl;
  43.     else
  44.     cout << f(0, a) << endl;
  45.     return 0;
  46. }
  47.  
Advertisement
RAW Paste Data Copied
Advertisement