Submission #1319382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319382		111	Knapsack (NOI18_knapsack)	C++20	0 / 100	0 ms	332 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int S,N;
    cin>>S>>N;

    static long long dp[2001];

    for(int i=0;i<=S;i++)
    {
        dp[i] = -LLONG_MAX;
    }
    dp[0] = 0;

    for(int i=1;i<=N;i++)
    {
        long long V,W,K;
        cin>>V>>W>>K;

        for(int r=0;r<W;r++)
        {
            deque<int>q;

            for(int s=r;s<=S;s+=W)
            {
                long long cur = dp[s] - (s-r)/W * V;

                while(!q.empty() && (s - q.front())/W > K)
                {
                    q.pop_front();
                }

                while(!q.empty() && dp[q.back()] - (q.back()-r)/W * V <= cur)
                {
                    q.pop_back();
                }

                q.push_back(s);

                dp[s] = dp[q.front()] + (s - q.front())/W * V;
            }
        }
    }

    long long ans=0;
    for(int i=0;i<=S;i++)
    {
        ans = max(ans, dp[i]);
    }

    cout<<ans;
    return 0;
}

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