Submission #1187889

#TimeUsernameProblemLanguageResultExecution timeMemory
1187889teokakabadzeKnapsack (NOI18_knapsack)C++20
73 / 100
1093 ms2632 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, w[N], k[N], v[N], s, dp[2003], p[2003], dp1[2003]; main() { std::ios::sync_with_stdio(0); cin.tie(0); cin >> s >> n; int i, j, st; for(i = 0; i < n; i++) cin >> v[i] >> w[i] >> k[i]; for(i = 0; i < n; i++) { for(st = s; st > max(-1ll, s - w[i]); st--) { int cnt = 0, r = st, l = st, p = 0; deque<int> d; while(r >= 0) { if(l >= 0) { while(d.size() && d.back() < dp[l] + (st - l) / w[i] * v[i]) d.pop_back(); d.push_back(dp[l] + (st - l) / w[i] * v[i]); dp1[l] = dp[l] + (st - l) / w[i] * v[i]; cnt++; } if(cnt == k[i] + 1 || l < 0) { if(d.size()) dp[r] = max(dp[r], d.front() - p * v[i]); if(d.front() == dp1[r]) d.pop_front(); // cout << r << ' ' << d.front() << ' ' << dp[r] << '\n'; r -= w[i]; cnt--; p++; } if(l >= 0) l -= w[i]; } } // cout << endl; } 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...