이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "iostream"
#include "vector"
#include "algorithm"
#include "queue"
#include "set"
#include "unordered_set"
#include "stack"
#include "map"
#include "limits.h"
#include "cstdio"
#include "math.h"
#include <numeric>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int limit, n;
cin>>limit>>n;
map<int, vector<pair<int,int>>> weight;
for(int i = 0; i<n; i++)
{
int value,wei,amt;
cin>>value>>wei>>amt;
if(wei<=limit&&amt>0)
weight[wei].push_back(make_pair(value,amt));
}
vector<vector<long long>> dp(weight.size()+1,vector<long long>(limit+1,INT32_MIN));
dp[0][0]=0;
int at = 1;
for(auto &[w,items]:weight)
{
sort(items.begin(),items.end(),greater<pair<int,int>>());
for(int i = 0; i<=limit; i++)
{
dp[at][i]=dp[at-1][i];
int copies = 0;
int typeat = 0;
int used = 0;
long long profit = 0;
while((copies+1)*w<=i&&typeat<items.size())
{
copies++;
profit+=items[typeat].first;
if(dp[at-1][i-copies*w]!=INT_MAX)
{
dp[at][i]= max(dp[at][i],dp[at-1][i-copies*w]+profit);
}
used++;
if(used == items[typeat].second)
{
used = 0;
typeat++;
}
}
}
at++;
}
cout<<*max_element(dp.back().begin(),dp.back().end());
}
컴파일 시 표준 에러 (stderr) 메시지
knapsack.cpp: In function 'int main()':
knapsack.cpp:33:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
33 | for(auto &[w,items]:weight)
| ^
knapsack.cpp:43:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | while((copies+1)*w<=i&&typeat<items.size())
| ~~~~~~^~~~~~~~~~~~~
# | 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... |