제출 #785641

#제출 시각아이디문제언어결과실행 시간메모리
7856410x34cKnapsack (NOI18_knapsack)C++17
100 / 100
106 ms2144 KiB
#include <bits/stdc++.h> #define ll long long #define pii pair<int, int> using namespace std; int main() { int S, N; cin >> S >> N; vector<vector<pii>> wei(S + 1); for (int i = 0; i < N; i++) { int v, w, k; cin >> v >> w >> k; wei[w].push_back({v, k}); } for (int i = 1; i <= S; i++) sort(wei[i].begin(), wei[i].end(), greater<pii>()); vector<int> vl, wi; for (int i = 1; i <= S; i++) { int idx = 0; for (int j = 0; j < S / i && idx < wei[i].size(); j++) { vl.push_back(wei[i][idx].first); wi.push_back(i); wei[i][idx].second--; if (wei[i][idx].second == 0) idx++; } } ll dp[2][S + 1]; int fr = 0, sc = 1; dp[0][0] = 0; for (int j = 1; j <= S; j++) { dp[0][j] = 0; if (wi[0] <= j) dp[0][j] = vl[0]; } for (int i = 1; i < vl.size(); i++) { for (int j = 0; j <= S; j++) { dp[sc][j] = dp[fr][j]; if (wi[i] <= j) dp[sc][j] = max(dp[sc][j], dp[fr][j - wi[i]] + vl[i]); } swap(fr, sc); } cout << dp[fr][S] << endl; }

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:29:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int j = 0; j < S / i && idx < wei[i].size(); j++)
      |                                      ~~~~^~~~~~~~~~~~~~~
knapsack.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 1; i < vl.size(); 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...