제출 #1346516

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1346516		SW_143	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	2824 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long int

using namespace std;

int main()
{   
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int S, N; cin>>S>>N; 
    
    vector<ll> wi(N+1), vi(N+1), ki(N+1);
    for(int i = 1; i<=N; ++i) cin>>vi[i]>>wi[i]>>ki[i];
    
    vector<ll> dp(S+1, 0);
    
    for(int i = 1; i<=N; ++i)
    {
        ll w = wi[i], v = vi[i], k = min(ki[i], S/wi[i]);
        vector<ll> ndp = dp;
        
        for(int r = 0; r < w; ++r)
        {
            deque<int> dq; 
            for(int j = r; j <= S; j += w)
            {
                ll t = (j - r) / w; 
                
                while(!dq.empty() && t - (dq.front()-r)/w > k)
                    dq.pop_front();
                
                while(!dq.empty() && dp[dq.back()] - ((dq.back()-r)/w)*v <= dp[j] - t*v)
                    dq.pop_back();
                
                dq.push_back(j);
                
                ndp[j] = dp[dq.front()] + (t - (dq.front()-r)/w) * v;
            }
        }
        dp = ndp;
    }
    
    cout<<dp[S]<<'\n';
    
    return 0;
}

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