Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int width, n;
- int steps[55];
- int dp[55][2002];
- int rec(int at, int position) {
- if(at == n) {
- return position;
- }
- if(dp[at][position] != -1) {
- return dp[at][position];
- }
- int result = -1;
- if(position - steps[at] >= 0) {
- result = max(result, rec(at + 1, position - steps[at]));
- }
- if(position + steps[at] <= width) {
- result = max(result, rec(at + 1, position + steps[at]));
- }
- return dp[at][position] = result;
- }
- int main()
- {
- int S;
- cin >> S >> width;
- cin >> n;
- for(int i = 0; i < n; i++) {
- cin >> steps[i];
- }
- for(int i = 0; i <= n; i++) {
- for(int j = 0; j <= 2000; j++) {
- dp[i][j] = -1;
- }
- }
- cout << rec(0, S) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement