제출 #500798

#제출 시각아이디문제언어결과실행 시간메모리
500798pancankesKnapsack (NOI18_knapsack)C++17
컴파일 에러
0 ms0 KiB
#include <iostream> #include <vector> #include <set> #include <map> using namespace std; #define ll long long const int MAXN=1e5+2; const int MOD=1e9+7; int main() { ll s,n; cin >> s >> n; // since s<=2000, and n<=1000000 // there will inevitably be repeated weights, so we can group them together map<int, vector<pair<int,int> > >weights; for (int i=0; i<n; i++) { int p,w,n; cin >> p >> w >> n; weights[w].push_back({p,n}); } vector<vector<int>> dp(weights.size()+1,vector<int>(s+1,0)); dp[0][0]=0; int at=1; for (auto& [w, items] : weights) { sort(items.rbegin(),items.rend()); for (int i=0; i<=s; i++) { dp[at][i]=dp[at-1][i]; int copies=0, j=0, cur=0; ll profit=0; // while there are items and while it is within the usable weight // we can use copies since all groups of items are of the same weight while ((copies+1) * w <= i && j<items.size()) { copies++; profit+=items[j].first; dp[at][i]=max((ll)dp[at][i],dp[at-1][i-copies*w]+profit); cur++; if (cur==items[j].second) { cur=0; j++; } } } at++; } // max_element gives a ptr to the value of the max element in a vector cout << *max_element(dp.back().begin(),dp.back().end()) << endl; }

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:29:9: error: 'sort' was not declared in this scope; did you mean 'qsort'?
   29 |         sort(items.rbegin(),items.rend());
      |         ^~~~
      |         qsort
knapsack.cpp:38:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             while ((copies+1) * w <= i && j<items.size())
      |                                           ~^~~~~~~~~~~~~
knapsack.cpp:54:14: error: 'max_element' was not declared in this scope
   54 |     cout << *max_element(dp.back().begin(),dp.back().end()) << endl;
      |              ^~~~~~~~~~~