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 int64_t
#define sz(x) (int)x.size()
#define MASK(i) ((1LL) << (i))
#define all(x) x.begin(), x.end()
#define BIT(x, i) ((x) >> (i) & (1LL))
#define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)
string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}
template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); }
const int MAXN = 1e5 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;
int n, s, f[2005];
struct dat {
int v, w, k;
dat (int _v = 0, int _w = 0, int _k = 0) {
v = _v, w = _w, k = _k;
}
} a[MAXN];
void solve() {
cin >> s >> n;
for (int i = 1; i <= n; i++) cin >> a[i].v >> a[i].w >> a[i].k;
for (int i = 1; i <= n; i++) {
int lim = min(a[i].k, s);
for (int j = 1; j <= lim; j++) {
for (int k = s; k >= a[i].w; --k)
maximize(f[k], f[k - a[i].w] + a[i].v);
}
}
cout << f[s];
}
#define TASK ""
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen(TASK".inp", "r", stdin);
//freopen(TASK".out", "w", stdout);
int ntest = 1;
//cin >> ntest;
while (ntest--) solve();
return 0;
}
//612
# | 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... |