This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef vector<int> vi;
const int INF = 1e9;
const int MX = 5e5 + 23;
const int MOD = 1e9+7;
const int MAX_N = 1e6;
const int MAX_N2 = 1e5;
const int TWO_MOD_INV = 500000004;
const int M = 998244353;
void solve() {
int n,s;
cin >> s >> n;
map<int, vector<pair<int,int>>>ma;
for(int i=0; i<n; ++i) {
int val, weight, am;
cin >> val >> weight >> am;
if(weight<=s && am) ma[weight].push_back({val, am});
}
vector<vector<ll>>dp(ma.size()+1, vector<ll>(s+1, INT32_MIN));
dp[0][0]=0;
int pos=1;
for(auto &[w, items]: ma) {
sort(items.begin(), items.end(), greater<pair<int,int>>());
for(int i=0; i<=s; ++i) {
dp[pos][s]=dp[pos-1][s];
int cnt=0, num=0, us=0;
ll profit=0;
while(cnt<items.size() && w*(num+1)<=i) {
++num;
profit+=items[cnt].first;
if(dp[pos-1][i-w*num]!=INT32_MIN) dp[pos][i]=max(dp[pos][i], dp[pos-1][i-w*num]+profit);
++us;
if(items[cnt].second==us) {
++cnt;
us=0;
}
}
}
++pos;
}
cout << *max_element(dp.back().begin(), dp.back().end()) << endl;
}
int main()
{
//freopen("feast.in","r",stdin);
//freopen("feast.out","w",stdout);
int t=1;
while(t--) solve();
return 0;
}
Compilation message (stderr)
knapsack.cpp: In function 'void solve()':
knapsack.cpp:28:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
28 | for(auto &[w, items]: ma) {
| ^
knapsack.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | while(cnt<items.size() && w*(num+1)<=i) {
| ~~~^~~~~~~~~~~~~
# | 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... |