Submission #1355016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1355016		kmath628	Knapsack (NOI18_knapsack)	C++20	100 / 100	45 ms	1720 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
int dp[2][2001];
vector<pair<int,int> > c[2001];
int main(){
    int s,n,v,w,k,i,j,j2,mx=0;
    scanf("%d %d",&s,&n);
    for(i=1;i<=n;i++){
        scanf("%d %d %d",&v,&w,&k);
        c[w].push_back({-v,k});
    }
    for(w=1;w<=s;w++){
        int cnt=0;
        sort(c[w].begin(),c[w].end());
        for(auto [v,k]:c[w]){
            for(j=0;j<=s;j++){
                for(j2=0;j2<=min(j/w,k);j2++){
                    dp[i%2][j]=max(dp[i%2][j],dp[(i-1)%2][j-w*j2]-v*j2);
                }
                mx=max(mx,dp[i%2][j]);
            }
            cnt+=k;i++;
            if(cnt>=s/w) break;
        }
    }
    printf("%d\n",mx);
    return 0;
}

Compilation message (stderr)

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