Submission #1053985

#TimeUsernameProblemLanguageResultExecution timeMemory
1053985ssitaramKnapsack (NOI18_knapsack)C++17
100 / 100
56 ms68176 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(nullptr); ll s, n; cin >> s >> n; vector<vector<ll>> items(s + 1); vector<tuple<ll, ll, ll>> init(n); for (ll i = 0; i < n; ++i) { cin >> get<0>(init[i]) >> get<1>(init[i]) >> get<2>(init[i]); } sort(init.rbegin(), init.rend()); for (ll i = 0; i < n; ++i) { ll v = get<0>(init[i]); ll w = get<1>(init[i]); ll k = get<2>(init[i]); while (items[w].size() <= s && k > 0) { items[w].push_back(v); --k; } } vector<vector<ll>> best(s + 1, vector<ll>(s + 1)); for (ll i = 1; i <= s; ++i) { for (ll j = 0; j <= s; ++j) { best[i][j] = best[i - 1][j]; ll amnt = 0; for (ll k = 0; k < items[i].size(); ++k) { amnt += items[i][k]; if (j - (k + 1) * i < 0) break; best[i][j] = max(best[i][j], best[i - 1][j - (k + 1) * i] + amnt); } } } cout << best[s][s] << '\n'; return 0; }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:20:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   20 |   while (items[w].size() <= s && k > 0) {
      |          ~~~~~~~~~~~~~~~~^~~~
knapsack.cpp:30:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    for (ll k = 0; k < items[i].size(); ++k) {
      |                   ~~^~~~~~~~~~~~~~~~~
#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...