题解

#include <bits/stdc++.h>
using namespace std;
const int OFFSET = 100000;
const int MAX_D = 200000;
const int INF = 1e9;
int main(){
    int n;
    cin >> n;
    vector<pair<int,int>> ingredients(n);
    for(int i = 0;i < n;i++){
        cin >> ingredients[i].first >> ingredients[i].second;
    }
    vector<vector<int>> dp(n + 1, vector<int>(MAX_D + 1,-INF));
    dp[0][OFFSET] = 0;
    for(int i = 1;i <= n;i++){
        int a = ingredients[i - 1].first;
        int b = ingredients[i - 1].second;
        int diff = a - b;
        for(int d = 0;d <= MAX_D;d++){
            if(dp[i - 1][d] != -INF){
                if(dp[i][d] < dp[i - 1][d]){
                    dp[i][d] = dp[i - 1][d];
                }
                int new_d = d + diff;
                if(0 <= new_d && new_d <= MAX_D){
                    if(dp[i][new_d] < dp[i - 1][d] + a + b){
                        dp[i][new_d] = dp[i - 1][d] + a + b;
                    }
                }
            }
        }
    }
    cout << max(0,dp[n][OFFSET]);
    return 0;
}