Submission #888909

#TimeUsernameProblemLanguageResultExecution timeMemory
888909Perl32Knapsack (NOI18_knapsack)C++14
0 / 100
1 ms348 KiB
//I wrote this code 4 u <3 #include <bits/stdc++.h> using namespace std; using ll = long long; #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif const int INF = (int) 1e9 + 1e3; const int maxN = 2024; ll dp[maxN]; vector<pair<int, int>> srt[maxN]; signed main(int32_t argc, char *argv[]) { ios_base::sync_with_stdio(false); cin.tie(nullptr); int W, n; cin >> W >> n; dp[0] = 0; for (int i = 0; i < n; ++i) { int s, w, k; cin >> s >> w >> k; k = min(s / w, k); srt[w].emplace_back(s, k); } for (auto &x : srt) { sort(x.rbegin(), x.rend()); } fill(dp + 1, dp + maxN, -INF); dp[0] = 0; for (int i = 1; i <= W; ++i) { for (auto [s, k] : srt[i]) { for (int l = W; l >= 0; --l) { for (int j = 1; j <= k; ++j) { if (l - k * j >= 0) { dp[l] = max(dp[l], dp[l - k * j] + 1ll * s * j); } } } } } ll mx = 0; for (int i = 0; i < maxN; ++i) { mx = max(mx, dp[i]); } cout << mx; } /* */

Compilation message (stderr)

knapsack.cpp: In function 'int main(int32_t, char**)':
knapsack.cpp:38:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         for (auto [s, k] : srt[i]) {
      |                   ^
#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...