Submission #1307084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307084		888313666	Knapsack (NOI18_knapsack)	C++20	29 / 100	79 ms	864 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,c;
vector<int> a, dp;
vector<vector<int>> pref, ct;
vector<vector<array<int, 2>>> p;

int find(const int w, const int k){
    //cout<<'a'<<endl;
    const auto m=ct[w].size();
    auto idx=lower_bound(ct[w].begin(), ct[w].end(), k)-ct[w].begin();
    if (ct[w][idx]>k) --idx;
    assert(idx>=0);
    //cout<<'c'<<endl;
    int sm=pref[w][idx];
    //cout<<'d'<<endl;
    //cout<<w<<' '<<idx+1<<' '<<m<<' '<<p[w][idx+1][0]<<' '<<k<<endl;
    //for (const auto [a, b]:p[w]) cout<<a<<' '<<b<<endl;
    sm+=p[w][idx][0]*(k-ct[w][idx]);
    //cout<<'b'<<endl;
    return sm;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    cin>>c>>n;
    a.assign(c+1, 0);
    p.assign(c+1, {{0,0}});
    pref.assign(c+1, {0});
    ct.assign(c+1, {0});
    dp.assign(c+1, 0);
    for (int i=0; i<n; i++){
        int v, w, k, t;
        cin>>v>>w>>k;
        p[w].push_back({v, k});
    }
    for (int w=1; w<=c; w++){
        sort(p[w].rbegin(), p[w].rend());
        const auto t=c/w;
        for (const auto [v, k]:p[w]){
            pref[w].push_back(pref[w].back()+min(t-a[w], k)*v);
            a[w]=min(t, a[w]+k);
            ct[w].push_back(a[w]);
        }
    }
    for (int i=1; i<=c; i++){
        for (int r=0; r<i; r++){
            deque<array<int, 2>> q;
            for (int j=r; j<=c; j+=i){
                if (!q.empty() && j-q.front()[0]>a[i]*i) q.pop_front();
                while (!q.empty() && q.back()[1]+find(i, (j-q.back()[0])/i)<=dp[j]) q.pop_back();
                q.push_back({j, dp[j]});
                const auto k=(j-q.front()[0])/i;
                dp[j]=max(dp[j], q.front()[1]+find(i, k));
            }
        }
    }
    cout<<dp.back()<<'\n';
}

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