Submission #1180906

#TimeUsernameProblemLanguageResultExecution timeMemory
1180906abdelaal_03Knapsack (NOI18_knapsack)C11
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef long long ll; const long double PI = 3.141592654; const long long md = 998244353; #define xi first #define yi second #define MAX 300007 #define INF (ll)1e18 #define SQ 500 long long gcd(long long a, long long b) { if (b == 0)return a; return (a % b) ? gcd(b, a % b) : b; } ll dp[1007][5000]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif ll n, W; cin>>n>>W; vector<ll> w(n + 1), v(n + 1), k(n + 1); for (int i = 1; i<= n; i++) { ll wi, vi, ki; cin>>vi>>wi>>ki; w[i] = wi; v[i] = vi; k[i] = ki; } for (int i = 1;i <= n; i++) { set<pair<ll, ll>>s[w[i]]; for (int j = 0; j <= W; j++){ dp[i][j] = dp[i - 1][j]; ll rem = j % w[i]; if (s[rem].size() > k[i]) { ll idx = j - (k[i] + 1) * w[i]; ll ow = dp[i - 1][idx] * w[i] - idx * v[i]; auto it = s[rem].find({ow, idx}); s[rem].erase(it); } if (!s[rem].empty()) dp[i][j] = max(dp[i][j], (s[rem].rbegin()->xi + j * v[i]) / w[i]); ll nw = dp[i - 1][j] * w[i] - j * v[i]; s[rem].insert({nw, j}); } } cout<<dp[n][W]<<endl; 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.