#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |