제출 #1033280

#제출 시각아이디문제언어결과실행 시간메모리
1033280vjudge1Knapsack (NOI18_knapsack)C++17
73 / 100
1051 ms1584 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i,n) for(int i=0;i<n;i++) #define ROF(i,m,n) for(int i=m;i<=n;i++) #define vi vector<int> #define pb push_back #define alle(a) a.begin(),a.end() #define rall(n) rbegin(n),rend(n) #define int long long #define vecs vector<int> #define ll long long #define ss second #define ff first const int INF = 1e9 + 1; const int MOD = 1e9 + 7; const int N = 2005; void solve() { int s, n; cin >> s >> n; vector<int> dp(s + 1, 0); for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; for (int b = 1; k > 0; b *= 2) { int num = min(b, k); k -= num; int tv = num * v; int tw = num * w; for (int j = s; j >= tw; j--) { dp[j] = max(dp[j], dp[j - tw] + tv); } } } cout << *max_element(dp.begin(), dp.end()); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; while (t--) { solve(); } 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...