제출 #919488

#제출 시각아이디문제언어결과실행 시간메모리
919488imannKnapsack (NOI18_knapsack)C++17
100 / 100
108 ms22608 KiB
#include <iostream> #include <vector> #include <cmath> #include <map> #include <algorithm> typedef long long ll; const int MAX_N = 1000*100 + 10; const int MAX_S = 2*1000 + 10; int Vs[MAX_N]; int Ws[MAX_N]; int Ks[MAX_N]; int dp[MAX_S][MAX_S]; struct Node { int w, k, v; bool operator > (const Node &n) const { return (v > n.v); } }; int solve(std::vector<std::vector<Node> > &wvec, int s) { for (auto &v : wvec) std::sort(v.begin(), v.end(), std::greater<Node>()); for (int i = 0; i < wvec.size(); ++i) { for (int j = 1; j <= s; ++j) { if (i > 0) dp[i][j] = dp[i - 1][j]; int wc = 0, vc = 0; for (auto v : wvec[i]) { if (wc > j) break; for (int k = 1; k <= v.k; k++) { vc += v.v; wc += v.w; if (wc > j) break; if (i > 0) dp[i][j] = std::max(dp[i][j], dp[i - 1][j - wc] + vc); else dp[0][j] = vc; } } } } return dp[wvec.size() - 1][s]; } int main() { int s, n; std::cin >> s >> n; for (int i = 0; i < n; ++i) { std::cin >> Vs[i] >> Ws[i] >> Ks[i]; } std::map<int, std::vector<Node> > wmap; for (int i = 0; i < n; ++i) wmap[Ws[i]].push_back({Ws[i], Ks[i], Vs[i]}); std::vector<std::vector<Node> > wvec; for (auto &v : wmap) wvec.push_back(v.second); std::cout << solve(wvec, s) << std::endl; }

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

knapsack.cpp: In function 'int solve(std::vector<std::vector<Node> >&, int)':
knapsack.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<Node> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (int i = 0; i < wvec.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...