제출 #1036797

#제출 시각아이디문제언어결과실행 시간메모리
1036797ocasuKnapsack (NOI18_knapsack)C++17
37 / 100
1094 ms488 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int inf=1e12; signed main(){ int S,n; cin>>S>>n; vector<multiset<int>> items(S+1); for (int i=0; i<n; i++){ int v,w,k; cin>>v>>w>>k; while (k>0 and (items[w].size()<=(S/w) or *(items[w].begin()) <= v)){ items[w].insert(v); if ((int)(items[w].size()) > S/w) items[w].erase(items[w].begin()); k--; } } vector<int> dp(S+1,-inf); //current maximum value of a subset with total weight w dp[0]=0; for (int w=0; w<=S; w++){ for (auto v: items[w]){ for (int i=S; i>=w; i--){ dp[i]=max(dp[i], dp[i-w]+v); } } } int ans=0; for (auto i: dp) ans=max(ans, i); cout<<ans<<'\n'; }

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:14:40: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   14 |         while (k>0 and (items[w].size()<=(S/w) or *(items[w].begin()) <= v)){
      |                         ~~~~~~~~~~~~~~~^~~~~~~
#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...