제출 #881516

#제출 시각아이디문제언어결과실행 시간메모리
881516androKnapsack (NOI18_knapsack)C++14
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> #define int long long using namespace std; signed main(){ ios::sync_with_stdio(false); cin.tie(0); int n,s; cin>>s>>n; int v[n+1]; int w[n+1]; int k[n+1]; for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>k[i]; vector<pair<int,int>>A[s+1]; for(int i=1;i<=n;i++)A[w[i]].push_back({v[i],k[i]}); vector<pair<int,int>>u; for(int i=1;i<=s;i++){ int mx=s/i; sort(A[i].begin(),A[i].end()); reverse(A[i].begin(),A[i].end()); for(auto it:A[i]){ if(mx<0)break; for(int j=1;j<=it.second;j++){ if(mx<0)break; u.push_back({it.first,i}); mx--; } } } /* int dp[u.size()][s+1]; for(int i=0;i<u.size();i++)for(int j=0;j<=s;j++)dp[i][j]=0; dp[0][u[0].second]=u[0].first; for(int i=1;i<u.size();i++){ for(int j=0;j<=s;j++)dp[i][j]=dp[i-1][j]; for(int j=u[i].second;j<=s;j++)dp[i][j]=max(dp[i][j],dp[i-1][j-u[i].second]+u[i].first); } int ans=0; for(int i=1;i<=s;i++)ans=max(ans,dp[u.size()-1][i]); cout<<ans;*/ vector<int>dp(s+1,0); vector<int>new_dp(s+1,0); new_dp[u[0].second]=u[0].first; for(int i=1;i<u.size();i++){ for(int j=0;j<=s;j++)dp[j]=new_dp[j]; for(int j=u[i].second;j<=s;j++)dp[j]=max(dp[j],new_dp[j-u[i].second]+u[i].first); swap(dp,new_dp); } int ans=0; for(int i=1;i<=s;i++)ans=max(ans,dp[i]); cout<<ans; } /* dobijas v[i] */

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:43:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=1;i<u.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...