Submission #1162376

#TimeUsernameProblemLanguageResultExecution timeMemory
1162376AlfraganusKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms1608 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define str string #define endl '\n' #define fs first #define ss second #define all(a) a.begin(), a.end() #define print(a) for(auto x : a) cout << x << ' '; cout << endl; #define printmp(a) for(auto x : a) cout << x[0] << ' ' << x[1] << endl; const int mod = 1e9 + 7; struct SegTree { int size = 1; vector<int> tree; SegTree (vector<int> &a){ while((int)a.size() > size) size <<= 1; tree.resize(size << 1); build(a, 0, 0, size); } void build(vector<int> &a, int x, int l, int r){ if(r - l == 1){ if(l < (int)a.size()) tree[x] = a[l]; return; } int mid = (l + r) >> 1; build(a, (x << 1) + 1, l, mid); build(a, (x << 1) + 2, mid, r); tree[x] = max(tree[(x << 1) + 1], tree[(x << 1) + 2]); } int get(int l, int r, int x, int lx, int rx){ if(l <= lx and rx <= r) return tree[x]; else if(r <= lx or rx <= l) return INT_MIN; int mid = (lx + rx) >> 1; return max(get(l, r, (x << 1) + 1, lx, mid), get(l, r, (x << 1) + 2, mid, rx)); } int get(int l, int r){ return get(l, r, 0, 0, size); } }; void solve(){ int s, n; cin >> s >> n; vector<int> v(n), w(n), k(n); for(int i = 0; i < n; i ++) cin >> v[i] >> w[i] >> k[i]; vector<int> dp(s + 1); for(int i = 0; i < n; i ++){ for(int j = 0; j < min(s + 1, w[i]); j ++){ vector<int> a; for(int x = 0; x * w[i] + j <= s; x ++) a.push_back(dp[x * w[i] + j] - x * v[i]); SegTree st(a); for(int x = 0; x * w[i] + j <= s; x ++){ int mx = st.get(max(0, x - k[i]), x + 1); dp[x * w[i] + j] = max(dp[x * w[i] + j], mx + x * v[i]); } } } cout << *max_element(all(dp)); } signed main(){ ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int t = 1; // cin >> t; while(t --){ solve(); cout << endl; } }
#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...