제출 #875697

#제출 시각아이디문제언어결과실행 시간메모리
875697tinnhiemnnKnapsack (NOI18_knapsack)C++14
0 / 100
8 ms31836 KiB
#include <bits/stdc++.h> using namespace std; #define file "file" #define pll pair<long long, long long> const long long N=2005, INF=1e9; long long W,n,i,j,k,v,w,sum,t,dem,dp[N][N],res; vector<pll> a[N]; int main() { //freopen(file".inp", "r", stdin); //freopen(file".out", "w", stdout); ios_base::sync_with_stdio(); cin.tie(); cin>>W>>n; for (i=1;i<=n;i++) { cin>>v>>w>>k; if (w<W && k>0) a[w].push_back({v, k}); } memset(dp, -0x3f, sizeof dp); dp[0][0]=0; i=1; for (w=1;w<=W;w++) { if (a[w].size()==0) continue; sort(a[w].begin(), a[w].end(), greater<pll>()); for (j=0;j<=W;j++) { dp[i][j]=dp[i-1][j]; sum=0; t=0; k=0; dem=0; while ((sum+1)*w <= j && k<a[w].size()) { sum++; t+=a[w][k].first; dem++; //cout<<w<<' '<<j<<' '<<k<<' '<<dem<<'\n'; if (dp[i-1][j-sum*w] > -INF) dp[i][j]=max(dp[i][j], dp[i-1][j-sum*w] + t); if (dem==a[w][k].second) k++, dem=0; } res=max(res, dp[i][j]); } i++; } cout<<res; }

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:37:39: 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]
   37 |             while ((sum+1)*w <= j && k<a[w].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...