Submission #881958

#	Time	Username	Problem	Language	Result	Execution time	Memory
881958		Azm1t	Knapsack (NOI18_knapsack)	C++17	100 / 100	113 ms	10248 KiB

knapsack

#include "bits/stdc++.h"
using namespace std;

#define rep(i, a, b) for (auto i = a; i < b; i++)
#define sz(x) static_cast<long long>((x).size())
#define all(x) (x).begin(), (x).end()

// #ifndef ONLINE_JUDGE
// #include "debug.h"
// #endif

#define int long long
#define double long double
const long long inf = (long long) 1e18;
const long long inf2 = LONG_LONG_MAX/2 - 100;
const long long mod = (int)1e9 + 7;


int32_t main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(10);

    int w, n; cin >> w >> n;
    vector<vector<int>> v[w+1];
    rep(i, 0, n){
        int x, y, z;  cin >> x >> y >> z;
        v[y].push_back({x, z});
    }

    rep(i, 1, w+1) sort(v[i].begin(), v[i].end());
    vector<vector<int>> a;

    for(int i = 1; i <= w; i++){
        int r = w/i + 5;
        for(int j = 0; j < r; j++){
            if(v[i].empty()) break;
            a.push_back({v[i].back()[0], i});
            v[i].back()[1]--;
            if(v[i].back()[1] == 0) v[i].pop_back();
        }
    }

    n = sz(a);
    vector<int> dp(w+1, 0), prevdp(w+1, 0);
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= w; j++){
            if(i == 0){
                if(j == a[i][1]) dp[j] = a[i][0];
            }
            else{
                dp[j] = prevdp[j];
                if(j >= a[i][1]) dp[j] = max(dp[j], prevdp[j-a[i][1]] + a[i][0]);
            }
        }
        prevdp = dp;
        dp.assign(w+1, 0);
    }

    int ans = *max_element(all(prevdp));
    cout << ans << '\n';


}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27