Submission #1195276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195276		lukasuliashvili	Knapsack (NOI18_knapsack)	C++17	73 / 100	1098 ms	136112 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define rep(i,a,b) for(int i=a; i<=b; i++) 
#define fs first 
#define sc second 
#define pb push_back
const int N=2*1e6;
const int R=2002;
int a[N],v[N],w[N],k[N],dp[N];
vector<pair<int,int>> vec[N];
signed main(){
    int n,s; cin>>s>>n;
    rep(i,1,n){cin>>v[i]>>w[i]>>k[i]; k[i]=min(k[i],R);}
    
    rep(i,1,n){
        int pow=1;
        int k2=k[i];
        while(pow<=k2){
            k2-=pow;
            pair<int,int> pr;
            pr.fs=v[i]*pow;
            pr.sc=w[i]*pow;
            vec[i].pb(pr);
            pow++;
            if(pow>k2 and k2!=0){
                pr.fs=v[i]*k2;
                pr.sc=w[i]*k2;
                vec[i].pb(pr);
            }
        }

    }
   
    // for(auto x:vec){
    //     cout<<x.fs<<" "<<x.sc<<" "<<endl;
    // }
    for(int kl=1; kl<=n; kl++){
        for(int i=0; i<vec[kl].size(); i++){
            for(int j=s; j>=vec[kl][i].sc; j--){
                dp[j]=max(dp[j-vec[kl][i].sc]+vec[kl][i].fs,dp[j]);
            }
        }
    }
    cout<<dp[s]<<endl;
    

}

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