이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Item{
int v, w, k;
bool operator<(const Item& o) const{
return v < o.v;
};
};
const int MAXN = 1e5 + 5, MAXS = 2000 + 5;
int maxW, n;
map<int, vector<Item>> arr;
ll dp[MAXS], pdp[MAXS];
int main(){
cin.tie(0)->sync_with_stdio(0);
//freopen("file.in", "r", stdin);
cin >> maxW >> n;
for (int i=0; i<n; i++){
int v, w, k;
cin >> v >> w >> k;
if (arr.find(w) == arr.end()){
arr.insert({w, vector<Item>()});
}
arr[w].push_back({v, w, k});
}
for (auto currW : arr){
vector<Item> curr = currW.second;
sort(curr.begin(), curr.end());
int iters = maxW/currW.first;
for (int j=0; j<iters && j < curr.size(); j++){
Item currItem = curr[j];
for (int i=1; i<=maxW; i++){
dp[i] = pdp[i];
for (int k=1; currItem.w*k<=i && k <= currItem.k; k++){
if (i >= (long)currItem.w*k){
dp[i] = max(dp[i], pdp[i-currItem.w*k] + (long)currItem.v*k);
}
}
}
for (int k=0; k<=maxW; k++){
pdp[k] = dp[k];
dp[k] = 0;
}
}
}
cout << pdp[maxW] << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
knapsack.cpp: In function 'int main()':
knapsack.cpp:32:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int j=0; j<iters && j < curr.size(); j++){
| ~~^~~~~~~~~~~~~
# | 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... |