Submission #629476

#	Time	Username	Problem	Language	Result	Execution time	Memory
629476		leeminhduc2	Knapsack (NOI18_knapsack)	C++17	73 / 100	1095 ms	1392 KiB

knapsack

#include <bits/stdc++.h>
#define ll int
#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 (int i=1;i<=s;i++) dp[i]=-1044266559;
    dp[0]=0;
    int res=dp[1];
    cerr << res;
    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);
                    res=max(res,dp[j]);
                }

            }
        }
    }
    cout << res;

}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    lulu_solution();
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27