Submission #973327

#	Time	Username	Problem	Language	Result	Execution time	Memory
973327		vjudge1	Knapsack (NOI18_knapsack)	C++14	100 / 100	49 ms	3056 KiB

knapsack

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int mxN = 1e5 + 5 , mxS = 2e3 + 5;

int n,s;
vector<pair<int,int>> bag[mxS];
ll dp[mxS];

int main(){

    scanf("%d %d",&s,&n);

    for(int i=1;i<=n;i++){
        int v,w,k;
        scanf("%d %d %d",&v,&w,&k);

        bag[w].push_back({v , min(k , s/w)});
    }

    for(int w=1;w<=s;w++) sort(bag[w].begin() , bag[w].end() , greater<pair<int,int>>());

    // for(int w=1;w<=s;w++){
    //     if(bag[w].empty()) continue;
    //     printf("w = %d : " , w);
    //     for(auto [v , k] : bag[w]) printf("%d %d , " , v , k);
    //     printf("\n");
    // }

    for(int w=1;w<=s;w++){
        if(bag[w].empty()) continue;

        int lim_k = s / w;
        int curr = bag[w][0].second , idx = 0;

        for(int k=1;k<=lim_k;k++){
            for(int cap=s;cap>=w;cap--) dp[cap] = max(dp[cap] , dp[cap - w] + bag[w][idx].first);

            if(k >= curr){
                idx++;
                curr += bag[w][idx].second;

                if(idx>= int(bag[w].size())) break;
            }
        }
    }

    printf("%lld" , dp[s]);

    return 0;
}

Compilation message (stderr)

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

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