Submission #1259730

#TimeUsernameProblemLanguageResultExecution timeMemory
1259730vuvietCloud Computing (CEOI18_clo)C++20
100 / 100
361 ms1352 KiB
#include <bits/stdc++.h> using namespace std; struct T { int c, f; long long v; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<T> a; int maxc = 0; for (int i = 0; i < n; i++) { T t; cin >> t.c >> t.f >> t.v; t.v = -t.v; a.push_back(t); maxc += t.c; } int m; cin >> m; for (int i = 0; i < m; i++) { T t; cin >> t.c >> t.f >> t.v; t.c = -t.c; a.push_back(t); } sort(a.begin(), a.end(), [](const T &x, const T &y) { return (x.f != y.f) ? x.f > y.f : x.v < y.v; }); const long long NEG = -4e18; vector<long long> dp(maxc + 1, NEG); dp[0] = 0; for (auto &t : a) { int start = (t.c > 0 ? maxc : 0); int end = (t.c > 0 ? t.c : maxc + t.c); int step = (t.c > 0 ? -1 : 1); for (int c = start; (t.c > 0 ? c >= end : c <= end); c += step) { int p = c - t.c; if (p >= 0 && p <= maxc && dp[p] != NEG) { dp[c] = max(dp[c], dp[p] + t.v); } } } cout << *max_element(dp.begin(), dp.end()) << "\n"; 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...