#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define pb push_back
#define lwb lower_bound
#define upb upper_bound
#define LL pair<ll, ll>
#define ii pair<int, int>
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define pqueue priority_queue
#define all(v) v.begin(), v.end()
#define szi(v) (int)(v.size())
#define szl(v) (ll)(v.size())
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//Time: cerr << "Time elapsed: " << TIME << " s.\n";
const ll mod = 1e9 + 7;
const int nmax = 1e5;
const ll inf = 1e18;
ll Pow(ll a, ll b){ if (!b || a == 1) return 1; if (!a) return 0; ll ans = 1; while (b){if (b & 1) ans *= a, ans %= mod; a *= a; a %= mod; b >>= 1;} return ans;}
ll Gcd(ll a, ll b){return (b ? Gcd(b, a % b) : a);}
bool minimize(int &a, int b){if (a > b){a = b; return 1;} return 0;}
bool maximize(ll &a, ll b){if (a < b){a = b; return 1;} return 0;}
void add(int &a, int b){a += b; if (a >= mod) a -= mod;}
void sub(int &a, int b){a -= b; if (a < 0) a += mod;}
int n, s;
//int w[2002], v[2002], c[2002];
int m = 0;
LL a[60002];
ll dp[2][60002];
int main(){
faster
freopen("MARKET.INP", "r", stdin);
freopen("MARKET.OUT", "w", stdout);
cin >> s >> n;
for (int i = 1; i <= n; i++){
int c = 1, p, h, k;
cin >> h >> p >> k;
while (k > c){
k -= c;
a[++m].fi = c * p;
a[m].se = c * h;
c <<= 1;
}
if (k){
a[++m].fi = k * p;
a[m].se = k * h;
}
}
for (int i = 1; i <= m; i++){
int cur = i & 1, last = cur ^ 1;
for (int j = 0; j <= s; j++){
dp[cur][j] = dp[last][j];
if (j >= a[i].fi) maximize(dp[cur][j], dp[last][j - a[i].fi] + a[i].se);
}
}
cout << dp[m & 1][s];
}
/*
!######### #
!########! ##!
!########! ###
!########## ####
######### ##### ######
!###! !####! ######
! ##### ######!
!####! #######
##### #######
!####! #######!
####!########
## ##########
,######! !#############
,#### ########################!####!
,####' ##################!' #####
,####' ####### !####!
####' #####
~## ##~
LONG LIVE THE GLORIOUS COMMUNIST PARTY OF VIET NAM
LONG LIVE THE SOCIALIST REPUBLIC OF VIET NAM
LONG LIVE GENERAL SECRETARY NGUYEN PHU TRONG
*/
Compilation message
knapsack.cpp: In function 'int main()':
knapsack.cpp:45:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | freopen("MARKET.INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:46:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | freopen("MARKET.OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
