Submission #1313975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313975		nambanana987	Knapsack (NOI18_knapsack)	C++20	73 / 100	1094 ms	2744 KiB

knapsack

#include <bits/stdc++.h>
#include <climits>
using namespace std;
#define f first
#define s second
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define int long long

struct info{
    int v,w,k;
};
const int N=1e5+5;
info M[N];
int s,n;
int dp[2000+5];
void solve(){
    cin>>s>>n;
    int ans=0;
    for(int i=1;i<=n;++i) cin>>M[i].v>>M[i].w>>M[i].k;
    for(int i=1;i<=n;++i){
        int remain=M[i].k;
        for(int k=1;remain>0;k<<=1){
            int take=min(k,remain);
            int wei=M[i].w*take,val=M[i].v*take;
            remain-=take;
            if(wei>s) continue;
            for(int j=s;j>=wei;--j){
                dp[j]=max(dp[j],dp[j-wei]+val);
                ans=max(ans,dp[j]);
            }
        }
    }
    cout<<ans;
}
signed main(){

    ios_base::sync_with_stdio(0);cin.tie(0);
    int T=1;
    while(T--) solve();
}

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