Submission #1261720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261720		mentarios	Knapsack (NOI18_knapsack)	C++20	73 / 100	33 ms	1860 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

/*ll dp(int i, int l, int x, int y, vector<ll>& memo, vector<ll>& v){
    if(i>=x or l>=v[x]) return 0;
    if(memo[i] != -1) return memo[i];
    ll n_c = 1000000;
    if(v[i] <= l) n_c = dp(i+1,l,x,y,memo,v);
    return memo[i] = min(dp(i+1, v[i]+y, x, y, memo,v)+1, n_c);
}

int main(){
    int x,y; cin >> x >> y;
    vector<ll> v(x);
    for(int i=0; i<x; i++) cin >> v[i];
    vector<ll> memo(x, -1);
    cout << dp(0,0,x,y,memo,v)<<endl;
    return 0;
}

*/

struct item{
    ll v,w;
};
const int maxn = 1e5;
item listt[maxn];
int main(){
    ll n, W;
    cin >> W >> n;
    const ll MOD = 1000000007;
    int index = 0;
    for(int i=1; i<=n; i++){
        ll p,h,k;
        cin >> h >> p >> k;
        ll c = 1;
        while(k>c){
            k-=c;
            listt[++index].w = c*p;
            listt[index].v = c*h;
            c*=2;
        }
        listt[++index].w = k*p;
        listt[index].v = k*h;
    }
    vector<ll> dp(W+1, 0);
    for(int i=1; i<=index; i++){
        for(int j=W; j>=listt[i].w; j--){
            dp[j] = max(dp[j], dp[j-listt[i].w] + listt[i].v);
        }
    }
    cout << dp[W] << endl;
}

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