Submission #1280336

#TimeUsernameProblemLanguageResultExecution timeMemory
1280336huy_initKnapsack (NOI18_knapsack)C++17
100 / 100
47 ms3020 KiB
#include <bits/stdc++.h> using namespace std; /*DEFINE*/ #define int long long #define MASK(x) (1LL << (x)) #define all(x) x.begin(), x.end() #define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__) const int MOD = 1e9 + 7; /*FUNTION*/ void ckmax(int &a, int b) { a = max(a, b); } void ckmin(int &a, int b) { a = min(a, b); } int gcd(int a, int b) { if (b==0) return a; return gcd(b, a%b); } int lcm(int a, int b) { return a/gcd(a,b)*b; } template<typename ...Args> void logger(string vars, Args&&... values) { cerr << vars << " = "; string delim = ""; (..., (cerr << delim << values, delim = ", ")); cerr << '\n'; } int binpow(int a, int b) { if (b == 0) return 1; int X = binpow(a, b / 2); if (b & 1) return X * X * a; return X * X; } struct item { int w, v, c; }; struct v { int w, v; }; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cerr.tie(nullptr); int t = 1; while (t--) { // code here int n, s; cin >> s >> n; map<int, vector<pair<int, int>>> mp; for (int i=0; i<n; i++) { int w, v, k; cin >> v >> w >> k; mp[w].push_back({v, k}); } vector<int> dp(s + 1, 0); for (int w=1; w<=s; w++) if (mp[w].size()) { int need = s / w; sort(all(mp[w])); for (int i=mp[w].size() - 1; i>=0; i--) // LIST ĐỒ VẬT CÓ TRỌNG LƯỢNG LÀ w { int v = mp[w][i].first; // giá trị v int k = mp[w][i].second; // có k đồ vật trọng lượng w if (need >= k) { need -= k; for (int i=1; i<=k; i++) { for (int sum=s; sum>=w; sum--) { ckmax(dp[sum], dp[sum - w] + v); } } } else { for (int i=1; i<=need; i++) { for (int sum=s; sum>=w; sum--) { ckmax(dp[sum], dp[sum - w] + v); } } break; } } } int cost = 0; for (int i=0; i<=s; i++) { ckmax(cost, dp[i]); } cout << cost << endl; } 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...