Advertisement
Josif_tepe

Untitled

Oct 31st, 2023
737
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.84 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. int width, n;
  5. int steps[55];
  6. int dp[55][2002];
  7. int rec(int at, int position) {
  8.     if(at == n) {
  9.         return position;
  10.     }
  11.     if(dp[at][position] != -1) {
  12.         return dp[at][position];
  13.     }
  14.     int result = -1;
  15.     if(position - steps[at] >= 0) {
  16.         result = max(result, rec(at + 1, position - steps[at]));
  17.     }
  18.     if(position + steps[at] <= width) {
  19.         result = max(result, rec(at + 1, position + steps[at]));
  20.     }
  21.     return dp[at][position] = result;
  22. }
  23. int main()
  24. {
  25.     int S;
  26.     cin >> S >> width;
  27.    
  28.     cin >> n;
  29.     for(int i = 0; i < n; i++) {
  30.         cin >> steps[i];
  31.     }
  32.    
  33.     for(int i = 0; i <= n; i++) {
  34.         for(int j = 0; j <= 2000; j++) {
  35.             dp[i][j] = -1;
  36.         }
  37.     }
  38.     cout << rec(0, S) << endl;
  39.     return 0;
  40. }
  41.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement