| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1274342 | kiteyu | Knapsack (NOI18_knapsack) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5;
const int M=2e6;
int s,n,n1=0;
struct node{
int v;
int w;
int k;
}a[N+5],b[M+5];
int dp[2005];
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>s>>n;
for(int i=1;i<=n;++i){
cin>>a[i].v>>a[i].w>>a[i].k;
a[i].k=min(a[i].k,s/a[i].w);
int fs = 0;
for(int j=10;j>=0;--j) if(((a[i].k >> j)&1)){
fs=j;
break;
}
for(int j=0;j<fs;++j){
b[++n1]={a[i].v,a[i].w,(1<<j)};
a[i].k-=(1<<j);
}
if(a[i].k)
b[++n1]=a[i];
}
//
// for(int i=1;i<=n1;++i)
// cout<<b[i].v<<' '<<b[i].w<<' '<<b[i].k<<'\n';
for(int i=1;i<=n1;++i){
int W=b[i].w*b[i].k;
int val=b[i].k*b[i].v;
// cout<<W<<' '<<val<<'\n';
for(int j=s-W;j>=0;--j){
// cout<<j<<','<<dp[i]+val<<'\n';
dp[j+W]=max(dp[j+W],dp[j]+val);
}
// for(int j=0;j<=s;++j) cout<<dp[j]<<' ';
// cout<<'\n';
}
ll ans=0;
for(int i=0;i<=s;++i)
ans=max(ans,dp[i]);
cout<<ans;
return 0;
}