Fundamente XI - Camion - 212

#include <bits/stdc++.h>
#define pi pair < int , int >
#define w first
#define p second

using namespace std;

inline void max_self(int& a, int b) {
    a = max(a, b);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, gmax;
    cin >> N >> gmax;
    vector < pi > a(N + 1);
    for(int i = 1; i <= N; ++i)
        cin >> a[i].w >> a[i].p;
    vector < int > dp(10001); // dp[x] = y <=> daca transporta x kilograme face maxim y profit
    int mx = 0;
    for(int i = 1; i <= N; ++i) { // iau pe rand fiecare obiect
        for(int j = mx; j >= 0; --j) // pornesc de la maxim pentru a fi sigur ca nu folosesc un obiect de mai multe ori
            if(dp[j + a[i].w] < dp[j] + a[i].p) { // pot transporta j + a[i].w si profitul nou ar putea fi dp[j] (profitul lui j) + a[i].p (profitul obiectului)
                dp[j + a[i].w] = dp[j] + a[i].p;
                max_self(mx, j + a[i].w);
            }
    }
    int ans = 0;
    for(int i = 0; i <= gmax; ++i)
        max_self(ans, dp[i]);
    cout << ans;
}