제출 #491330

#제출 시각아이디문제언어결과실행 시간메모리
491330DDTerziev04Knapsack (NOI18_knapsack)C++14
12 / 100
1 ms584 KiB
#include<iostream> #include<vector> #include<algorithm> using namespace std; const int MAXN=1e5, MAXS=2000; long long dp[MAXS+1]; vector<pair<int, int> > v[MAXS]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); long long s, n; cin >> s >> n; for(int i=0; i<n; i++) { int p, w, h; cin >> p >> w >> h; v[w].push_back({p, h}); } for(int i=0; i<=s; i++) { sort(v[i].begin(), v[i].end()); reverse(v[i].begin(), v[i].end()); dp[i]=-1; } dp[0]=0; long long ans=0; for(int i=1; i<=s; i++) { if(v[i].size()==0) { continue; } for(int j=s; j>=0; j--) { int idx=0, p=0, h=v[i][0].second; for(int u=1; u*i<=j; u++) { if(u>h) { idx++; if(idx==v[i].size()) { break; } h+=v[i][idx].second; } p+=v[i][idx].first; if(dp[j-u*i]==-1) { continue; } dp[j]=max(dp[j], dp[j-u*i]+p); } ans=max(ans, dp[j]); } } cout << ans << "\n"; return 0; }

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:52:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |                     if(idx==v[i].size())
      |                        ~~~^~~~~~~~~~~~~
#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...