제출 #1191824

#제출 시각아이디문제언어결과실행 시간메모리
1191824sunboiCloud Computing (CEOI18_clo)C++20
0 / 100
1 ms396 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = (1LL<<60); int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<tuple<int,int,ll>> comps(n); ll totalC = 0; set<int> freq; for(int i=0;i<n;i++){ int ci; ll fi, vi; cin >> ci >> fi >> vi; comps[i] = make_tuple(ci, (int)fi, vi); totalC += ci; freq.insert(fi); } int m; cin >> m; vector<tuple<int,int,ll>> orders(m); for(int j=0;j<m;j++){ int Cj; ll Fj, Vj; cin >> Cj >> Fj >> Vj; orders[j] = make_tuple(Cj, (int)Fj, Vj); freq.insert(Fj); } // compress and sort frequencies descending vector<int> Freq(freq.begin(), freq.end()); sort(Freq.rbegin(), Freq.rend()); // group computers and orders by frequency unordered_map<int, vector<int>> comp_by_f; for(int i=0;i<n;i++){ auto &[ci, fi, vi] = comps[i]; comp_by_f[fi].push_back(i); } unordered_map<int, vector<int>> ord_by_f; for(int j=0;j<m;j++){ auto &[Cj, Fj, Vj] = orders[j]; ord_by_f[Fj].push_back(j); } // DP arrays int MAXC = totalC; vector<ll> minCost(MAXC+1, INF), orderDP(MAXC+1, -INF); minCost[0] = 0; orderDP[0] = 0; ll answer = 0; // sweep frequencies for(int f: Freq){ // add all computers with fi == f for(int idx: comp_by_f[f]){ auto &[ci, fi, vi] = comps[idx]; for(int c = MAXC - ci; c >= 0; --c){ if(minCost[c] < INF){ minCost[c + ci] = min(minCost[c + ci], minCost[c] + vi); } } } // add all orders with Fj == f for(int idx: ord_by_f[f]){ auto &[Cj, Fj, Vj] = orders[idx]; for(int c = MAXC; c >= Cj; --c){ orderDP[c] = max(orderDP[c], orderDP[c - Cj] + Vj); } } // update answer at this frequency threshold for(int c = 0; c <= MAXC; ++c){ if(minCost[c] < INF && orderDP[c] > -INF){ answer = max(answer, orderDP[c] - minCost[c]); } } } cout << answer << "\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...