Submission #1178535

#TimeUsernameProblemLanguageResultExecution timeMemory
1178535HezovKnapsack (NOI18_knapsack)C++20
29 / 100
2 ms1100 KiB
#include <iostream> using namespace std; int dp[100001][2001], v[2001], w[2001], k[2001]; int main() { int S, N; cin >> S >> N; for(int i = 1;i<=N;i++) cin >> v[i] >> w[i] >> k[i]; for(int i = 0;i<=N;i++) { for(int j = 0;j<=S;j++) { if(i == 0 || j == 0) dp[i][j] = 0; else { dp[i][j] = dp[i-1][j]; int nr = min(k[i], j / w[i]); int st = 0, dr = nr, mid; while(st<=dr) { mid = (st + dr) / 2; int val = dp[i-1][j - w[i] * mid] + v[i] * mid; if(val >= dp[i][j]) dp[i][j] = val, st = mid+1; else dr = mid-1; } } } } cout << dp[N][S]; return 0; }
#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...