제출 #875971

#제출 시각아이디문제언어결과실행 시간메모리
875971androKnapsack (NOI18_knapsack)C++14
73 / 100
146 ms262144 KiB
#include <bits/stdc++.h> #define int long long using namespace std; signed main(){ ios::sync_with_stdio(false); cin.tie(0); int S,n; 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]; if(n==1){ cout<<min(K[1],S/W[1])*V[1]; return 0; } int ok=1; for(int i=1;i<=n;i++)if(K[i]!=1)ok=0; /* if(ok){ int dp[n+1][S+1]; for(int i=0;i<=n;i++)for(int j=0;j<=S;j++)dp[i][j]=0; for(int i=1;i<=n;i++){ for(int j=0;j<=S;j++)dp[i][j]=dp[i-1][j]; for(int j=W[i];j<=S;j++){ dp[i][j]=max(dp[i][j],dp[i-1][j-W[i]]+V[i]); } } int ans=0; for(int i=1;i<=S;i++){ ans=max(ans,dp[n][i]); } cout<<ans; return 0; }*/ int dp[n+1][S+1]; for(int i=0;i<=n;i++)for(int j=0;j<=S;j++)dp[i][j]=0; for(int i=1;i<=n;i++){ for(int j=0;j<=S;j++)dp[i][j]=dp[i-1][j]; for(int j=W[i];j<=S;j++){ for(int k=1;k<=K[i];k++){ if(j-k*W[i]<0)break; dp[i][j]=max(dp[i][j],dp[i-1][j-k*W[i]]+k*V[i]); } } } int ans=0; for(int i=1;i<=S;i++){ ans=max(ans,dp[n][i]); } cout<<ans; }

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:17:9: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   17 |     int ok=1;
      |         ^~
#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...