제출 #1307052

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307052		888313666	Knapsack (NOI18_knapsack)	C++20	0 / 100	301 ms	263152 KiB

knapsack

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

signed main(){
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int c,n;
    cin>>c>>n;
    //cout<<'a'<<endl;
    vector<int> a(c+1,0);
    //cout<<'b'<<endl;
    vector<vector<int>> pref(c+1, vector<int>(1, 0));
    //cout<<'c'<<endl;
    for (int i=0; i<n; i++){
        int v, w, k;
        cin>>v>>w>>k;
        if ((a[w]+k)*w>c) {
            const auto t=a[w];
            for (int j=t+1; j<=t+k; j++){
                if (j*w>c) break;
                pref[w].push_back(pref[w].back()+v);
                ++a[w];
            }
        } else {
            for (int j=a[w]+1; j<=a[w]+k; j++){
                pref[w].push_back(pref[w].back()+v);
            }
            a[w]+=k;
        }
    }
    vector<int> dp(c+1, 0);
    for (int i=1; i<=c; i++){
        if (!a[i]) continue;
        for (int j=0; j<i; j++){
            deque<pair<int, int>> q;
            for (int k=j; k<=c; k+=i){
                if (!q.empty() && k-q.front().first>i*a[i]) q.pop_front();
                while (!q.empty() && q.back().second+pref[i][(k-q.back().first)/i]<=dp[k]) q.pop_back();
                q.emplace_back(k, dp[k]);
                const auto t=(k-q.front().first)/i;
                dp[k]=max(dp[k], q.front().second+pref[i][t]);
            }
        }
    }
    cout<<dp.back()<<'\n';
}

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