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>
using namespace std;
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 1e9 + 7;
const int N = 1e5;
main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int s, n; cin >> s >> n;
vector<int> dp(s+1, LLONG_MIN);
vector<pair<int, int> > items[s+1];
vector< vector<int> > weights(s+1, vector<int>(s+1, 0));
dp[0] = 0;
for(int i = 1;i <= n; i++){
int V, W, K; cin >> V >> W >> K;
items[W].push_back({V, K});
}
for(int i = 1;i <= s; i++){
sort(all(items[i]));
for(int j = 1;j <= s && items[i].size(); j++){
weights[i][j] = weights[i][j-1] + items[i].back().ff;
items[i].back().ss--;
if(items[i].back().ss == 0) items[i].pop_back();
}
}
for(int i = 1;i <= s; i++){
for(int d = s; d>= 0; d--){
for(int round = 1; d-round * i >= 0 && round <= s; round++){
dp[d] = max(dp[d], dp[d-round*i] + weights[i][round]);
}
}
}
int ans = LLONG_MIN;
for(int i = 0;i <= s; i++){
ans = max(ans, dp[i]);
}
cout << ans;
return 0;
}
Compilation message (stderr)
knapsack.cpp:11:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
11 | main(){
| ^~~~
# | 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... |