#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pb push_back
struct informasi
{
ll v, w, stock;
};
int main()
{
ll s, n;
cin >> s >> n;
vector<informasi> v(n);
for (ll i = 0; i < n; i++)
{
cin >> v[i].v >> v[i].w >> v[i].stock;
}
vector<pair<ll, ll>> dp[n + 1];
dp[0].pb({s, 0});
set<ll> has[n + 1];
for (ll i = 1; i <= n; i++)
{
for (auto j : dp[i - 1])
{
ll cnt = 0;
for (ll w = j.first; w >= max(0LL, j.first - v[i - 1].stock * v[i - 1].w); w -= v[i - 1].w)
{
if (!has[i].count(w))
{
dp[i].pb({w, j.second + cnt * v[i - 1].v});
has[i].insert(w);
}
else
{
ll l = 0, r = dp[i].size() - 1;
while (l < r)
{
ll mid = (l + r) / 2;
if (dp[i][mid].first == w)
{
ll incremeter = j.second + cnt * v[i - 1].v;
dp[i][mid].second = max(dp[i][mid].second, incremeter);
break;
}
else if (dp[i][mid].first < w)
l = mid;
else
r = mid;
}
}
sort(dp[i].begin(), dp[i].end());
cnt++;
}
}
}
ll ans = 0;
for (auto i : dp[n])
{
ans = max(ans, i.second);
}
cout << ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
3 ms |
604 KB |
Output is correct |
3 |
Correct |
3 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Execution timed out |
1000 ms |
7156 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
3 ms |
604 KB |
Output is correct |
3 |
Correct |
3 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Execution timed out |
1000 ms |
7156 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
3 ms |
604 KB |
Output is correct |
7 |
Correct |
3 ms |
604 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Execution timed out |
1000 ms |
7156 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
3 ms |
604 KB |
Output is correct |
7 |
Correct |
3 ms |
604 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Execution timed out |
1000 ms |
7156 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |