제출 #1344458

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1344458		a0ms1n	Knapsack (NOI18_knapsack)	C++20	73 / 100	1094 ms	16732 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long 

int s,n;
vector<pair<int,int>> arr;

int dp[(int)2005]={0};

signed main(){
    cin>>s>>n;
    for(int i=1;i<=n;i++){
        int w,v,k;
        cin>>v>>w>>k;
        k = min(k,s/w);
        int cur = 1;
        while(k>=cur){
            arr.push_back({w*cur,v*cur});
            k -= cur;
            cur*=2;
        }
        if(k!=0)arr.push_back({w*k,v*k});
    }
    int N = arr.size();
    int ans = 0;
    for(int i=0;i<N;i++){
        for(int w=0;w<=s-arr[i].first;w++){
            dp[w] = max(dp[w],dp[w+arr[i].first]+arr[i].second);
            ans = max(dp[w],ans);
        }
    }
    
    cout<<ans<<'\n';
    return 0;
}

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