제출 #881942

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
881942		Azm1t	Knapsack (NOI18_knapsack)	C++17	37 / 100	1086 ms	166364 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()



#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;
    rep(i, 0, n){
        int x, y, z;  cin >>  x >> y >> z;
        int cur = 1;
        while(cur <= z){
            v.push_back({x*cur, y*cur, cur});
            z -= cur;
        }
        if(z > 0) v.push_back({x*z, y*z, cur});
    }

    n = sz(v);
    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 == v[i][1]) dp[j] = v[i][0];
            }
            else{
                dp[j] = prevdp[j];
                if(j >= v[i][1]) dp[j] = max(dp[j], prevdp[j-v[i][1]] + v[i][0]);
            }
        }
        prevdp = dp;
        dp.assign(w+1, 0);
    }

    int ans = *max_element(all(prevdp));

    cout << ans << '\n';


}

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