제출 #1354770

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1354770		askelad	Knapsack (NOI18_knapsack)	C++20	73 / 100	1093 ms	500 KiB

knapsack

#include<bits/stdc++.h>

#define ll  long long

using namespace std;


// void SolveBoundedKnapsack(ll &dp[] ,int w, int v, int c, int W){

//     ll next_dp[W] = dp;

//     for(int r=0;r<w;r++){
//         deque<pair<ll, int>>dq;
//         for(int q = 0; q*w+r <= W; q++){
//             ll cur_val = dp[q*w+r] - q*v;

//             while(!dq.empty() && dq.back().first <= cur_val)dq.pop_back();
//             dq.push_back({cur_val,q});

//             if(dq.front().second < q-c)dq.pop_front();

//             next_dp[q*w+r] = dq.front().first + q*v ;

//         }
//     }

//     dp = next_dp;

// }


void solve(int test){
    int W,n;
    cin>>W>>n;

    ll dp[2][W+1]={};

    #define c1 (bool)(i&1)
    #define c2 (bool)(!c1)
    
    int w,v,c;
    for(int i=1;i<=n;i++){
        cin>>v>>w>>c;
        for(int r=0;r<w;r++){
            deque<pair<ll, int>>dq;
            for(int q = 0; q*w+r <= W; q++){
                ll cur_val = dp[c2] [q*w+r] - q*v;

                while(!dq.empty() && dq.back().first <= cur_val)dq.pop_back();
                dq.push_back({cur_val,q});

                if(dq.front().second < q-c)dq.pop_front();

                dp[c1] [q*w+r] = dq.front().first + q*v ;

            }
        }
    
    }

    ll ans=0;
    for(auto x:dp[n&1])ans=max(ans,x);
    cout<<ans;

}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;

    // cin>>t;
    for(int i=1;i<=t;i++)
        solve(i);
}

• 서브태스크 1: 12 / 12
• 서브태스크 2: 17 / 17
• 서브태스크 3: 20 / 20
• 서브태스크 4: 24 / 24
• 서브태스크 5: 0 / 27