제출 #1331394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1331394		kride024	Knapsack (NOI18_knapsack)	C++20	73 / 100	1093 ms	408 KiB

knapsack

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

vector<long long>dp;


int main() {
long long s,n;
cin>>s>>n;
dp.assign(s+1,0);

for(int i=0;i<n;i++){
    long long v1,w1,k1;
    cin>>v1>>w1>>k1;
    for(long long j=1;j<=k1;j*=2){
        long long new_v=v1*j;
        long long new_w=w1*j;
        
        for(long long curr=s;curr>=new_w;curr--){
            dp[curr]=max(dp[curr],new_v+dp[curr-new_w]);
        }
        k1-=j;
    }
    if(k1>0){
         long long new_v=v1*k1;
         long long new_w=w1*k1;
        for(long long curr=s;curr>=new_w;curr--){
            dp[curr]=max(dp[curr],new_v+dp[curr-new_w]);
        }
    }
}


cout<<dp[s]<<endl;
}

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