CCCPaste

Untitled

#include 

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;
}