This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define db long double
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio\
ios_base::sync_with_stdio(0);\
cin.tie(0);\
cout.tie(0)\
#define int long long
int dp[2005], n, m, x, y, z;
vii w[2005];
signed main(){
fastio;
cin >> m >> n;
for(int i = 1; i <= n; i++){
cin >> x >> y >> z;
w[y].push_back({x, z});
}
for(int i = 1; i <= m; i++){
sort(all(w[i]));
reverse(all(w[i]));
while(w[i].size() > m / i) w[i].pop_back();
}
for(int i = 1; i <= m; i++){
for(pii j : w[i]){
for(int z = 1; z <= j.second; z++){
for(int k = m; k >= i; k--){
dp[k] = max(dp[k], dp[k - i] + j.first);
}
}
}
}
cout << dp[m];
}
Compilation message (stderr)
knapsack.cpp: In function 'int main()':
knapsack.cpp:37:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
37 | while(w[i].size() > m / i) w[i].pop_back();
| ~~~~~~~~~~~~^~~~~~~
# | 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... |