#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <iomanip>
#include <cstring>
#include <stdio.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<long long> vll;
typedef pair<ll,ll> pll;
#define double long double
const double eps = 1e-9;
#define FOR(i,a,b) for(long long i=a;i<b;i++)
#define all(v) v.begin(),v.end()
template <typename I>
void print(vector<I> &v){
FOR(i,0,v.size()){cout << v[i] << " ";}
cout << "\n";
}
ll gcd(ll a,ll b){
if(a==0){return b;}
else if(b==0){return a;}
else if(a<b){return gcd(b%a,a);}
else{return gcd(a%b,b);}
}
ll lcm(ll a,ll b){
return (a/gcd(a,b))*b;
}
void setIO(string name = "") {
freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
freopen((name + ".out").c_str(), "w", stdout);
}
void init_code(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
}
void solve(){
// store very big numbers may mean log2
ll s,n;
cin >> s >> n;
vector<vll> price_weight_quant(n,vll(3));
FOR(i,0,n){
FOR(j,0,3) cin >> price_weight_quant[i][j];
}
vector<vll> dp1(s+1,vll(s+1,INT_MIN));
FOR(i,0,s+1){
dp1[i][0] = 0;
}
vector<vector<pll>> weight_wise(s+1);
FOR(i,0,n){
weight_wise[price_weight_quant[i][1]].push_back({price_weight_quant[i][0],price_weight_quant[i][2]});
}
FOR(i,0,s+1){
sort(weight_wise[i].rbegin(),weight_wise[i].rend());
}
FOR(i,1,s+1){
if(weight_wise[i].empty()) continue;
ll left = 0;
ll curr = 0;
while((curr<s)&&(left<weight_wise[i].size())){
ll addi = weight_wise[i][left].second;
FOR(j,curr+1,min(addi+curr+1,s+1)){
dp1[i][j] = dp1[i][j-1]+weight_wise[i][left].first;
}
curr += addi;
left++;
}
}
vll dp(s+1,0);
FOR(i,1,s+1){
for(ll w=s;w>0;w--){
for(ll j=0;(i*j)<=w;j++){
if(dp1[i][j]==INT_MIN) continue;
dp[w] = max(dp[w],dp[w-(i*j)]+dp1[i][j]);
}
}
}
cout << (*max_element(all(dp))) << "\n";
}
signed main(){
//setIO
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// init_code();
ll t=1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
Compilation message (stderr)
knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:44:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp: In function 'void init_code()':
knapsack.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | freopen("input.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:49:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | freopen("output.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |