Submission #713614

#	Time	Username	Problem	Language	Result	Execution time	Memory
713614		NNerver	Knapsack (NOI18_knapsack)	C++14	73 / 100	1080 ms	2712 KiB

knapsack

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

const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;

int N,S;
int v[MAXN],w[MAXN],k[MAXN];
int dp[MAXN];

void update(int V,int W){
    for(int i=S;i>=W;i--){
        dp[i]=max(dp[i],dp[i-W]+V);
    }
}

int main(){
    scanf("%d%d",&S,&N);
    for(int i=1;i<=N;i++){
        scanf("%d%d%d",&v[i],&w[i],&k[i]);
    }
    for(int i=1;i<=N;i++){
        int K=min(k[i],S/w[i]);
        int cnt=1;
        for(;cnt<=K;cnt*=2){
            update(v[i]*cnt,w[i]*cnt);
            K-=cnt;
        }
        update(v[i]*K,w[i]*K);
    }
    printf("%d\n",dp[S]);

    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d%d",&S,&N);
      |     ~~~~~^~~~~~~~~~~~~~
knapsack.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d%d%d",&v[i],&w[i],&k[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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