제출 #1053976

#제출 시각아이디문제언어결과실행 시간메모리
1053976ssitaramKnapsack (NOI18_knapsack)C++17
73 / 100
1065 ms4188 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct item { ll v, w, k; }; int main() { ios::sync_with_stdio(0); cin.tie(nullptr); ll s, n; cin >> s >> n; vector<item> v(n); for (ll i = 0; i < n; ++i) { cin >> v[i].v >> v[i].w >> v[i].k; } vector<ll> best(s + 1); for (ll i = 0; i < n; ++i) { vector<set<pair<ll, ll>>> prevs(v[i].w); vector<ll> valof(s + 1); vector<ll> prbest = best; ll last = 3001; for (ll j = 0; j <= s; ++j) { if (!(j % v[i].w)) --last; valof[j] = best[j] + v[i].v * last; prevs[j % v[i].w].insert({valof[j], j}); if (prevs[j % v[i].w].size() == v[i].k + 2) { ll idx = j - v[i].w * (v[i].k + 1); prevs[j % v[i].w].erase({valof[idx], idx}); } ll bestidx = (*prev(prevs[j % v[i].w].end())).second; best[j] = prbest[bestidx] + (j - bestidx) / v[i].w * v[i].v; } } cout << best.back() << '\n'; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

knapsack.cpp: In function 'int main()':
knapsack.cpp:28:33: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   28 |    if (prevs[j % v[i].w].size() == v[i].k + 2) {
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
#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...