Submission #1195218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195218		lukasuliashvili	Knapsack (NOI18_knapsack)	C++17	73 / 100	1095 ms	2680 KiB

knapsack

// Source: https://usaco.guide/general/io

#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*1e5+3;
const int R=2002;
int a[N],v[N],w[N],k[N],dp[N];
vector<pair<int,int>> vec;
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.pb(pr);
            pow++;
            if(pow>k2 and k2!=0){
                pr.fs=v[i]*k2;
                pr.sc=w[i]*k2;
                vec.pb(pr);
            }
        }
        for(int i1=0; i1<vec.size(); i1++){
            for(int j=s; j>=vec[i1].sc; j--){
                dp[j]=max(dp[j-vec[i1].sc]+vec[i1].fs,dp[j]);
            }
        }
        vec.clear();

    }
   
    // for(auto x:vec){
    //     cout<<x.fs<<" "<<x.sc<<" "<<endl;
    // }
    // for(int i=0; i<vec.size(); i++){
    //     for(int j=s; j>=vec[i].sc; j--){
    //         dp[j]=max(dp[j-vec[i].sc]+vec[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