Submission #957372

#TimeUsernameProblemLanguageResultExecution timeMemory
957372DipaKnapsack (NOI18_knapsack)C++14
100 / 100
115 ms4220 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 1e9 + 7; int main(int argc, char const *argv[]) { int S, N; cin >> S >> N; map<int, vector<pair<int, int>>> m; vector<pair<int, int>> eff; for (int i = 0; i < N; i++) { int v, w, k; cin >> v >> w >> k; m[w].push_back({v, k}); } for (auto &[w, vec]: m) { sort(vec.begin(), vec.end()); } for (auto &[w, vec]: m) { int limit = S/w; while (limit > 0 && vec.size() > 0) { --limit; eff.push_back({vec.back().first, w}); --vec.back().second; if (vec.back().second == 0) vec.pop_back(); } } ll dp[S + 1]{0}; for (auto &[v, w]: eff) { for (int i = S; i >= 0; --i) { if (i - w < 0) continue; dp[i] = max(dp[i], dp[i - w] + v); } } ll ans = 0; for (int i = 0; i <= S; ++i) { ans = max(ans, dp[i]); } cout << ans << '\n'; return 0; }

Compilation message (stderr)

knapsack.cpp: In function 'int main(int, const char**)':
knapsack.cpp:28:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |     for (auto &[w, vec]: m) {
      |                ^
knapsack.cpp:35:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |     for (auto &[w, vec]: m) {
      |                ^
knapsack.cpp:49:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |     for (auto &[v, w]: eff) {
      |                ^
#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...