제출 #907239

#제출 시각아이디문제언어결과실행 시간메모리
907239heeheeheehaawCloud Computing (CEOI18_clo)C++17
100 / 100
383 ms2176 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") using namespace std; struct event { int tip, a, b, cost; }; vector<event> events; const long long INF = 1e13; bool cmp(event a, event b) { if(a.b != b.b) return a.b > b.b; else return a.tip < b.tip; } long long dp[100005], newdp[100005]; signed main() { ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n, q; cin>>n; for(int i = 1; i <= n; i++) { int a, b, c; cin>>a>>b>>c; events.push_back({1, a, b, c}); } cin>>q; for(int i = 1; i <= q; i++) { int a, b, c; cin>>a>>b>>c; events.push_back({2, a, b, c}); } sort(events.begin(), events.end(), cmp); int sum = 0; for(auto it : events) { if(it.tip == 1) { sum += it.a; for(int i = 0; i <= sum; i++) { newdp[i] = -INF; if(i<=sum-it.a) newdp[i] = dp[i]; int last = i - it.a; if(last >= 0) newdp[i] = max(newdp[i], dp[last] - it.cost); } } else { for(int i = 0; i <= sum; i++) { newdp[i] = dp[i]; int nx = i + it.a; if(nx <= sum) newdp[i] = max(newdp[i], dp[nx] + it.cost); } } for(int i = 0; i <= sum; i++) dp[i] = newdp[i]; } long long maxx = 0; for(int i = 0; i <= sum; i++) maxx = max(maxx, dp[i]); cout<<maxx<<'\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...