Submission #1188449

#TimeUsernameProblemLanguageResultExecution timeMemory
1188449teokakabadzeKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms488 KiB
#include<bits/stdc++.h> #define f first #define s second #define pb push_back #define int long long #define pii pair<int, int> using namespace std; const int N = 5e5 + 5, M = 1e9 + 7; int T, n, s, dp[2003]; main() { std::ios::sync_with_stdio(0); cin.tie(0); cin >> s >> n; for(int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; for(int st = 0; st < w; st++) { deque<pii> d; for(int j = 0, ind = st; ind <= s; j++, ind += w) { int val = dp[ind] - j * v; while(!d.empty() && d.back().f <= val) d.pop_back(); d.pb({val, j}); while(d.size() && d.front().s < j - k) d.pop_front(); dp[ind] = d.front().f + j * v; } } } cout << dp[s] << '\n'; }

Compilation message (stderr)

knapsack.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 | main()
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...