Just壁垒

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_ROUND = 105;
const int MAX_BLOCK = 10005;
int dp[MAX_ROUND][MAX_BLOCK];
const int INF = -100000000;

int main()
{
    int n;
    cin >> n;
    int V[105], D[105];
    for (int i = 1; i <= n; ++i)
    {
        cin >> V[i] >> D[i];
    }
    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j < MAX_BLOCK; ++j)
        {
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i)
    {
        for (int last = 0; last < MAX_BLOCK; ++last)
        {
            if (dp[i-1][last] == INF)
                continue;
            int after = last + V[i] - D[i];
            if (after >= 0 && after < MAX_BLOCK)
            {
                dp[i][after] = max(dp[i][after], dp[i-1][last]);
            }
            after = last - D[i];
            if (after >= 0)
            {
                dp[i][after] = max(dp[i][after], dp[i-1][last] + last);
            }
        }
    }

    int ans = INF;
    for (int x = 0; x < MAX_BLOCK; ++x)
    {
        ans = max(ans, dp[n][x]);
    }

    if (ans < 0)
        cout << -1 << endl;
    else
        cout << ans << endl;

    return 0;
}