#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ld eps = 1e-8;
// for matching the kactl notes
#define sz(x) ((int)x.size())
#define rep(i,a,b) for (int i = (int)(a); i < (int)(b); ++i)
#define all(a) (a).begin(), (a).end()
// #define constexpr(...) (__VA_ARGS__)
// DEBUGING TEMPLETE ////////////////////////////////////////////////////////////////////////{{{
#define db(val) "["#val" = "<<(val)<<"] "
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL_DEBUG
# define clog cerr << flush << string(__db_level * 2, ' ')
# define DB() debug_block CONCAT(dbbl, __LINE__)
int __db_level = 0;
struct debug_block {
debug_block() { clog << "{" << endl; ++__db_level; }
~debug_block() { --__db_level; clog << "}" << endl; }
};
#else
# define clog if (0) cerr
# define DB(...)
#endif
template<class U, class V> ostream& operator<<(ostream& out, const pair<U, V>& p) {
return out << "(" << p.first << ", " << p.second << ")";
}
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
if constexpr(i == tuple_size<T>::value) return out << ")";
else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup);
}
template<class ...U> ostream& operator<<(ostream& out, const tuple<U...>& tup) {
return print_tuple_utils<0, tuple<U...>>(out, tup);
}
template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator<<(ostream& out, const Con& container) {
out << "{";
for (auto it = container.begin(); it != container.end(); ++it)
out << (it == container.begin() ? "" : ", ") << *it;
return out << "}";
}
// ACTUAL SOLUTION START HERE ////////////////////////////////////////////////////////////////}}}
const ll inf = 1e16;
int main() {
#ifdef LOCAL
freopen("main.inp", "r", stdin);
freopen("main.out", "w", stdout);
freopen(".log", "w", stderr);
#endif
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int s, n;
cin >> s >> n;
vector<ll> dp(s + 1, -inf);
dp[0] = 0;
while (n--) {
ll v;
int w, k;
cin >> v >> w >> k;
vector<ll> new_dp = dp;
rep(i, 0, s + 1) dp[i] -= v * (i / w);
rep(rem, 0, w) {
deque<int> qu;
for (int i = rem; i <= s; i += w) {
while (qu.size() and (i - qu[0]) / w > k) qu.pop_front();
while (qu.size() and (dp[qu.back()] <= dp[i])) qu.pop_back();
qu.push_back(i);
new_dp[i] = max(new_dp[i], dp[qu[0]] + v * (i / w));
}
}
swap(dp, new_dp);
}
cout << *max_element(all(dp));
return 0;
}
// vim: foldmethod=marker
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
320 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
6 ms |
344 KB |
Output is correct |
3 |
Correct |
6 ms |
340 KB |
Output is correct |
4 |
Correct |
12 ms |
332 KB |
Output is correct |
5 |
Correct |
11 ms |
332 KB |
Output is correct |
6 |
Correct |
8 ms |
332 KB |
Output is correct |
7 |
Correct |
10 ms |
352 KB |
Output is correct |
8 |
Correct |
8 ms |
332 KB |
Output is correct |
9 |
Correct |
11 ms |
340 KB |
Output is correct |
10 |
Correct |
8 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
6 ms |
344 KB |
Output is correct |
3 |
Correct |
6 ms |
340 KB |
Output is correct |
4 |
Correct |
12 ms |
332 KB |
Output is correct |
5 |
Correct |
11 ms |
332 KB |
Output is correct |
6 |
Correct |
8 ms |
332 KB |
Output is correct |
7 |
Correct |
10 ms |
352 KB |
Output is correct |
8 |
Correct |
8 ms |
332 KB |
Output is correct |
9 |
Correct |
11 ms |
340 KB |
Output is correct |
10 |
Correct |
8 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
6 ms |
332 KB |
Output is correct |
13 |
Correct |
6 ms |
332 KB |
Output is correct |
14 |
Correct |
11 ms |
332 KB |
Output is correct |
15 |
Correct |
11 ms |
332 KB |
Output is correct |
16 |
Correct |
8 ms |
332 KB |
Output is correct |
17 |
Correct |
8 ms |
332 KB |
Output is correct |
18 |
Correct |
8 ms |
332 KB |
Output is correct |
19 |
Correct |
8 ms |
332 KB |
Output is correct |
20 |
Correct |
11 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
320 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
6 ms |
344 KB |
Output is correct |
7 |
Correct |
6 ms |
340 KB |
Output is correct |
8 |
Correct |
12 ms |
332 KB |
Output is correct |
9 |
Correct |
11 ms |
332 KB |
Output is correct |
10 |
Correct |
8 ms |
332 KB |
Output is correct |
11 |
Correct |
10 ms |
352 KB |
Output is correct |
12 |
Correct |
8 ms |
332 KB |
Output is correct |
13 |
Correct |
11 ms |
340 KB |
Output is correct |
14 |
Correct |
8 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
6 ms |
332 KB |
Output is correct |
17 |
Correct |
6 ms |
332 KB |
Output is correct |
18 |
Correct |
11 ms |
332 KB |
Output is correct |
19 |
Correct |
11 ms |
332 KB |
Output is correct |
20 |
Correct |
8 ms |
332 KB |
Output is correct |
21 |
Correct |
8 ms |
332 KB |
Output is correct |
22 |
Correct |
8 ms |
332 KB |
Output is correct |
23 |
Correct |
8 ms |
332 KB |
Output is correct |
24 |
Correct |
11 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
5 ms |
332 KB |
Output is correct |
27 |
Correct |
6 ms |
332 KB |
Output is correct |
28 |
Correct |
11 ms |
348 KB |
Output is correct |
29 |
Correct |
11 ms |
332 KB |
Output is correct |
30 |
Correct |
8 ms |
332 KB |
Output is correct |
31 |
Correct |
10 ms |
340 KB |
Output is correct |
32 |
Correct |
8 ms |
352 KB |
Output is correct |
33 |
Correct |
8 ms |
332 KB |
Output is correct |
34 |
Correct |
8 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
320 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
6 ms |
344 KB |
Output is correct |
7 |
Correct |
6 ms |
340 KB |
Output is correct |
8 |
Correct |
12 ms |
332 KB |
Output is correct |
9 |
Correct |
11 ms |
332 KB |
Output is correct |
10 |
Correct |
8 ms |
332 KB |
Output is correct |
11 |
Correct |
10 ms |
352 KB |
Output is correct |
12 |
Correct |
8 ms |
332 KB |
Output is correct |
13 |
Correct |
11 ms |
340 KB |
Output is correct |
14 |
Correct |
8 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
6 ms |
332 KB |
Output is correct |
17 |
Correct |
6 ms |
332 KB |
Output is correct |
18 |
Correct |
11 ms |
332 KB |
Output is correct |
19 |
Correct |
11 ms |
332 KB |
Output is correct |
20 |
Correct |
8 ms |
332 KB |
Output is correct |
21 |
Correct |
8 ms |
332 KB |
Output is correct |
22 |
Correct |
8 ms |
332 KB |
Output is correct |
23 |
Correct |
8 ms |
332 KB |
Output is correct |
24 |
Correct |
11 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
5 ms |
332 KB |
Output is correct |
27 |
Correct |
6 ms |
332 KB |
Output is correct |
28 |
Correct |
11 ms |
348 KB |
Output is correct |
29 |
Correct |
11 ms |
332 KB |
Output is correct |
30 |
Correct |
8 ms |
332 KB |
Output is correct |
31 |
Correct |
10 ms |
340 KB |
Output is correct |
32 |
Correct |
8 ms |
352 KB |
Output is correct |
33 |
Correct |
8 ms |
332 KB |
Output is correct |
34 |
Correct |
8 ms |
332 KB |
Output is correct |
35 |
Correct |
36 ms |
1348 KB |
Output is correct |
36 |
Execution timed out |
1089 ms |
696 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |