Submission #1255809

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

knapsack

#include <bits/stdc++.h>


#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
#define change_io() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define el endl
#define all(x) begin(x), end(x)
#define pb push_back
#define mp make_pair
#define INF 1000000005
#define LLINF 1e18
#define MOD 1000000007
#define MOD9 998244353

// remove single val from multiset with -> os.find_by_order(os.order_of_key(x))
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pair_set;

const ll N5 = 1e5 + 5;
const ll N6 = 1e6 + 5;
const ll NN5=2e5+5;
const ll N3=1e3+5;
ll dp[2005] {};
void solve()
{
    int s, n; cin >> s >> n;
    ll v[n], k[n], w[n];
    for (int i = 0; i < n; ++i) {
        cin >> v[i] >> w[i] >> k[i];
    }
    for (int i = 0; i < n; ++i) {
        deque<array<ll, 2>> prev[w[i]];
        ll water = 0;
        for (ll j = 0; j <= s; ++j) {
            ll md = j%w[i];
            while (!prev[md].empty() && prev[md].front()[0]+water<=dp[j]) {
                prev[md].pop_front();
            }
            prev[md].push_front({dp[j]-water, j});
            while (!prev[md].empty() && prev[md].back()[1]<j-k[i]*w[i]) {
                prev[md].pop_back();
            }

            dp[j] = max(dp[j], prev[md].back()[0]+water);

            if (md == w[i]-1) {
                water+=v[i];
            }
        }
    }

    ll ans = 0;
    for (int i = 0; i <= s; ++i) {
        ans = max(ans, dp[i]);
    }

    cout << ans << el;
}

int main()
{
	//freopen("problemname.in", "r", stdin);
	//freopen("problemname.out", "w", stdout);
    change_io();

    ll T;
    T=1;
    //cin>>T;
    while (T--)
    {
            solve();
    }
    return 0;
}

Compilation message (stderr)

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