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>
#define ll long long
#define ft first
#define sc second
using namespace std;
const int N=1e5+10;
ll s,n,v[N],w[N],k[N],dp[N];
void lulu_solution()
{
cin >> s >> n;
for (ll i=1;i<=n;i++)
{
cin >> v[i] >> w[i] >> k[i];
for (ll st=0;st<w[i];st++){
deque<pair<ll,ll>> dq;
for (ll j=st;j<=s;j+=w[i])
{
ll prev=dp[j]-((j-st)/w[i])*v[i];
while (dq.size()&&(j-dq.front().ft)/w[i]>k[i]) dq.pop_front();
while (dq.size()&&dq.back().sc<prev) dq.pop_back();
dq.push_back({j,prev});
if (j!=st)
{
dp[j]=max(dp[j],((j-st)/w[i])*v[i]+dq.front().sc);
}
}
}
}
cout << *max_element(dp,dp+s);
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
lulu_solution();
}
# | 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... |