Submission #713622

#	Time	Username	Problem	Language	Result	Execution time	Memory
713622		NNerver	Knapsack (NOI18_knapsack)	C++14	100 / 100	290 ms	4864 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 cntw[MAXN];
int v[MAXN],w[MAXN],k[MAXN];
vector<pair<int, pair<int,int> > > vec;
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]);
        vec.push_back({-v[i],{w[i],k[i]}});
    }
    sort(vec.begin(),vec.end());
    for(int i=0;i<N;i++){
        int V=-vec[i].first;
        int W=vec[i].second.first;
        int kk=vec[i].second.second;
        int K=min(kk,S/W);
        if(cntw[W]>=S) continue;
        cntw[W]+=kk;
        int cnt=1;
        for(;cnt<=K;cnt*=2){
            update(V*cnt,W*cnt);
            K-=cnt;
        }
        update(V*K,W*K);
    }
    printf("%d\n",dp[S]);

    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d%d",&S,&N);
      |     ~~~~~^~~~~~~~~~~~~~
knapsack.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         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: 27 / 27