제출 #689421

#제출 시각아이디문제언어결과실행 시간메모리
689421tcmmichaelb139Knapsack (NOI18_knapsack)C++17
0 / 100
1 ms468 KiB
#include "bits/stdc++.h" using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int s, n; cin >> s >> n; vector<vector<pair<long long, long long>>> v(s + 1); for (int i = 0; i < n; i++) { int a, b, c; cin >> a >> b >> c; if (c == 0 || b > s) continue; v[b].push_back({a, c}); } long long dp[s + 1]; for (int i = 0; i <= s; i++) dp[i] = -1; dp[0] = 0; for (int i = 1; i <= s; i++) { sort(rbegin(v[i]), rend(v[i])); if (v[i].size() == 0) continue; for (int j = s; j >= 0; j--) { if (dp[j] == -1) continue; long long cur = j; long long num = 0; long long done = 0; long long val = 0; while (cur <= s) { if (v[i][num].second == done) num++, done = 0; if (num == v[i].size()) break; cur += i; val += v[i][num].first; done++; dp[cur] = max(dp[cur], dp[j] + val); } } } cout << *max_element(dp, dp + s + 1) << '\n'; }

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:36:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |                 if (num == v[i].size()) break;
      |                     ~~~~^~~~~~~~~~~~~~
#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...