Submission #1282141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282141		Faisal_Saqib	Knapsack (NOI18_knapsack)	C++20	73 / 100	1098 ms	70124 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
const int N=1e5+100;
const ll inf=1e18;
int w[N],v[N],k[N];
ll dp[N],ad[N];
vector<ll> vec[N];
deque<int> cur[N];
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int s,n;
    cin>>s>>n;
    for(int i=0;i<n;i++)
    {
        cin>>v[i]>>w[i]>>k[i];
        k[i]=min(2000ll,k[i]);
    }
    // dp[i][s] = max value 
    // dp[i][s]  = dp[i-1][s] take no elements
    // dp[i][s] = dp[i-1][s-w[i]]+v[i] 1 ele
    // dp[i][s] = max(dp[i-1][s-k*w[i]]+v[i]*k)
    for(int i=0;i<n;i++)
    {
        // dp[x] = max(dp[x-w[i]])
        for(int idp=0;idp<=s;idp++)
        {
            if(idp<w[i])
            {
                // [0,s] 
                // how many with mod w[i] =idp
                // idp+k*w[i] <=s
                // k <= (s-idp)/w[i]
                vec[idp].clear();
                int tlp=(s-idp)/w[i]; // tlp>=0
                vec[idp].reserve(tlp+1);
                cur[idp].clear();
                // cur[idp].reserve(k[i]);
                ad[idp]=0;
            }
            int x=idp%w[i];
            vec[x].push_back(dp[idp]);
            // ll ad=0;
            for(int j=vec[x].size()-1;j<vec[x].size();j++)
            {
                ad[x]+=v[i];
                // cur[0]>= cur[1]>=cur[2]
                while(cur[x].front()<j-k[i])
                    cur[x].pop_front();
                vec[x][j]-=ad[x];
                while(cur[x].size()>0 and vec[x][cur[x].back()]<vec[x][j])
                    cur[x].pop_back();
                cur[x].push_back(j);
                    // cur[x].insert(vec[x][j]-ad[x]);
                if(cur[x].size()>0)
                    dp[idp]=vec[x][cur[x].front()]+ad[x];
            }
        }
    }
    ll mx=0;
    for(int i=0;i<=s;i++)mx=max(mx,dp[i]);
    cout<<mx<<endl;
}

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