Submission #1192565

#TimeUsernameProblemLanguageResultExecution timeMemory
1192565NeltCloud Computing (CEOI18_clo)C++20
54 / 100
868 ms2264 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define endl "\n" using namespace std; using namespace __gnu_pbds; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T, typename key = less<T>> using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>; const ll MAX = 2005 * 50; ll dp[MAX], ndp[MAX]; void solve() { ll n; cin >> n; vector<array<ll, 4>> a; while (n--) { ll c, f, v; cin >> c >> f >> v; a.push_back({f, c, v, 0}); } cin >> n; while (n--) { ll c, f, v; cin >> c >> f >> v; a.push_back({f, c, v, 1}); } sort(a.begin(), a.end(), greater()); for (ll i = 1; i < MAX; i++) dp[i] = -1e18; for (auto [_, c, v, tp] : a) { for (ll i = 0; i < MAX; i++) ndp[i] = -1e18; for (ll i = 0; i < MAX; i++) if (i + (tp == 0 ? c : -c) < MAX and i + (tp == 0 ? c : -c) >= 0) ndp[i + (tp == 0 ? c : -c)] = max(ndp[i + (tp == 0 ? c : -c)], dp[i] + (tp == 0 ? -v : v)); for (ll i = 0; i < MAX; i++) dp[i] = max(dp[i], ndp[i]); } ll ans = -1e18; for (ll i = 0; i < MAX; i++) ans = max(ans, dp[i]); cout << ans << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll t = 1; // precomp(); // cin >> t; for (ll cs = 1; cs <= t; cs++) solve(); // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n"; }
#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...