이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
* author : Apiram
* created: 12.08.2024 23:08:11
*/
#include<bits/stdc++.h>
using namespace std;
struct node{
long long v,w,k;
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
long long s,n;cin>>s>>n;
vector<node>arr(n);
for (long long i = 0;i<n;++i){
cin>>arr[i].v>>arr[i].w>>arr[i].k;
}
vector<long long>dp(s + 1,0);
dp[0] = 0;
long long ans = 0;
for (long long i = 0;i<n;++i){
vector<long long>pos;
for (long long k = 0;;++k){
if (arr[i].k < (1LL<<k))break;
pos.push_back((1LL<<k));
arr[i].k-=(1LL<<k);
}
if (arr[i].k != 0)pos.push_back(arr[i].k);
sort(pos.begin(),pos.end());
for (auto x:pos){
for (long long j = s;j>=0;--j){
if (j - x * arr[i].w < s)break;
dp[j] = max(dp[j],dp[j - x * arr[i].w] + arr[i].v * x);
}
}
//for (int j = 0;j<=s;++j)cout<<dp[j]<<" ";
//cout<<'\n';
}
sort(dp.begin(),dp.end());
cout<<dp.back()<<'\n';
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
knapsack.cpp: In function 'int main()':
knapsack.cpp:21:12: warning: unused variable 'ans' [-Wunused-variable]
21 | long long ans = 0;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |