제출 #1049789

#제출 시각아이디문제언어결과실행 시간메모리
1049789MarkTYZhangKnapsack (NOI18_knapsack)C++17
37 / 100
3 ms8796 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long ll V[3000005],W[3000005]; ll dp[100001]; int zero_one_knapsack(){ int s,n; cin >> s >> n; int index = 0; for (int i=1;i<=n;i++){ int v,w,k; cin >> v >> w >> k; int j = 1; while (k>=j){ V[++index] = v * j; W[index] = w * j; k -= j; j *= 2; } if (k>0){ V[++index] = v * k; W[index] = w * k; } } for (int i=1;i<=index;i++){ for (int j=s;j>=W[i];j--){ if (j-W[i]<0) break; dp[j] = max(dp[j], dp[j-W[i]] + V[i]); } } return dp[s]; } int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cout << zero_one_knapsack(); 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...