#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ins insert
#define F first
#define S second
#define MAXN 100005
#define LOG (int)log2(MAXN)+1
const int INF = 1e18;
const int MOD = 998244353;
const double EPS = 1e-8;
int N, S;
void slv(){
vector<pair<int, int>> a;
for(int i = 0; i < N; i++){
int p, w, k;
cin >> p >> w >> k;
for(int i = 0; i < k; i++) a.pb({p, w});
}
vector<vector<int>> dp(a.size()+1, vector<int>(S+1));
for(int i = 1; i <= a.size(); i++){
for(int j = 1; j <= S; j++){
dp[i][j] = dp[i-1][j];
if(j>=a[i-1].S) dp[i][j] = max(dp[i][j], dp[i-1][j-a[i-1].S]+a[i-1].F);
}
}
cout << dp[a.size()][S] << '\n';
}
void solve(){
cin >> S >> N;
if(N!=1){
slv();
return;
}
int p, w, k;
cin >> p >> w >> k;
cout << min(S/w, k)*p << '\n';
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
//cin >> t;
while(t--) solve();
return 0;
}
# | 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... |