Submission #1226983

#TimeUsernameProblemLanguageResultExecution timeMemory
1226983yassiaCloud Computing (CEOI18_clo)C++20
100 / 100
625 ms2292 KiB
#ifndef local #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("O3") #endif #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; using ll = long long; #define int ll using pll = pair<ll,ll>; using str = string; using ld = long double; auto sd = std::chrono::high_resolution_clock::now().time_since_epoch().count(); mt19937 rnd(sd); ll dp[100005]; ll dp1[100005]; ll inf = -1e18; void solve1() { for (auto &x: dp){ x = inf; } for (auto &x : dp1){ x = inf; } ll n;cin>>n; int C = 0; vector<vector<ll>> events; for (int i =0; i < n; i++){ int ci, fi, vi; cin>>ci>>fi>>vi; events.push_back({fi, 1, ci, vi}); C += ci; } ll m; cin>> m; for (int i =0; i <m ;i++){ int ci, fi, vi; cin>>ci>>fi>>vi; events.push_back({fi, 0, ci, vi}); } sort(events.rbegin(), events.rend()); dp[0]= 0; for (auto &ev : events) { int ci = ev[2]; int vi = ev[3]; int type = ev[1]; if (type == 0) { for (int j = 0; j <= C-ci; j++){ if (dp[j+ci]==inf)continue; dp1[j] = max(dp1[j], dp[j+ci]+vi); } } else { for (int j = ci; j <= C; j++){ if (dp[j-ci]==inf)continue; dp1[j] = max(dp1[j], dp[j-ci]-vi); } } for (int j = 0 ;j <= C; j++){ dp1[j] = max(dp1[j],dp[j]); } for (int i = 0; i <= C; i++){ dp[i] = dp1[i]; dp1[i] = inf; } } int G = 0; for (int i = 0; i <= C; i++){ G =max(G, dp[i]); } cout<<G; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); #ifdef local freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif ll t1 = 1; for (int _ = 0; _ < t1; ++_) solve1(); #ifdef local printf_s("\n%.5f s", (double) clock() / CLOCKS_PER_SEC); #endif }
#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...