Submission #1354776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1354776		askelad	Knapsack (NOI18_knapsack)	C11	Compilation error	0 ms	0 KiB

knapsack

#include<bits/stdc++.h>

#define ll  long long

using namespace std;


void SolveBoundedKnapsack(vector<int>&dp ,int w, int v, int c, int W){

    vector<int> next_dp = dp;

    for(int r=0;r<w;r++){
        deque<pair<int, int>>dq;
        for(int q = 0; q*w+r <= W; q++){
            int 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 s,n;
    cin>>s>>n;

    vector<int>dp(s+1,0);

    int w,v,c;
    while(n--){
        cin>>v>>w>>c;
        SolveBoundedKnapsack(dp,w,v,c,s);
    }

    int ans=0;
    for(auto x:dp)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);
}

Compilation message (stderr)

knapsack.c:1:9: fatal error: bits/stdc++.h: No such file or directory
    1 | #include<bits/stdc++.h>
      |         ^~~~~~~~~~~~~~~
compilation terminated.