Submission #1265803

#TimeUsernameProblemLanguageResultExecution timeMemory
1265803canhnam357Cloud Computing (CEOI18_clo)C++20
100 / 100
224 ms1096 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define MASK(i) (1LL << (i)) const int MAXN = 1e5 + 5; const int inf = 1e18; const int block = 320; struct pc { int c, f, v; void in() { cin >> c >> f >> v; } bool operator<(pc o) const { return f > o.f; } }; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; vector<pc> b, s; cin >> n; b.resize(n); int sum = 0; for (auto& x : b) x.in(), sum += x.c; cin >> m; s.resize(m); for (auto& x : s) x.in(); sort(b.begin(), b.end()); sort(s.begin(), s.end()); vector<int> dp(sum + 1, -inf); dp[0] = 0; int cur_sum = 0; for (int i = 0, j = 0; i < m; i++) { while (j < n && b[j].f >= s[i].f) { cur_sum += b[j].c; for (int k = cur_sum; k >= b[j].c; k--) { dp[k] = max(dp[k], dp[k - b[j].c] - b[j].v); } j++; } for (int k = s[i].c; k <= cur_sum; k++) { dp[k - s[i].c] = max(dp[k] + s[i].v, dp[k - s[i].c]); } } cout << *max_element(dp.begin(), dp.end()); 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...
#Verdict Execution timeMemoryGrader output
Fetching results...