제출 #638047

#제출 시각아이디문제언어결과실행 시간메모리
638047zandlerKnapsack (NOI18_knapsack)C++14
73 / 100
8 ms596 KiB
#include <bits/stdc++.h> using namespace std; int dp[2001]; pair<pair<int,int>,int> a[2001]; vector<int> pref[2001]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int s, n; cin >> s >> n; for(int i=0;i<n;i++){ cin >> a[i].first.first >> a[i].first.second; cin >> a[i].second; } sort(a, a+n); for(int i=n-1;i>=0;i--){ //cout << a[i].second << ' '; int v = a[i].first.second; for(int j=0;j<a[i].second && v*pref[v].size()<s;j++){ int st = 0; if(pref[v].size()){ st = pref[v].back(); } pref[v].push_back(st); pref[v].back()+=a[i].first.first; } } // for(int i=1;i<=s;i++){ // cout << pref[i].size() << ' '; // } for(int i=1;i<=s;i++){ for(int j=s;j>=0;j--){ for(int x=pref[i].size()-1; x>=0; x--){ if(j+(x+1)*i<= s){ //cout << j+x*i << '\n'; dp[j+(x+1)*i]=max(dp[j+(x+1)*i],dp[j]+pref[i][x]); } } } } cout << *max_element(dp,dp+s+1) << '\n'; return 0; }

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:19:54: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |         for(int j=0;j<a[i].second && v*pref[v].size()<s;j++){
      |                                      ~~~~~~~~~~~~~~~~^~
#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...