Submission #906215

#TimeUsernameProblemLanguageResultExecution timeMemory
906215LudisseyCloud Computing (CEOI18_clo)C++14
36 / 100
3065 ms262144 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

int n,m;
vector<pair<pair<int,int>,int>> table;
map<pair<int,int>,int> memo;

bool comp(pair<pair<int,int>,int> a, pair<pair<int,int>,int> b){
    if(a.first.second==b.first.second) return a.first.first>b.first.first;
    return a.first.second>b.first.second;
}

int dp(int x, int clck){
    if(memo.find({x,clck})!=memo.end()) return memo[{x,clck}];
    if(clck<0) return -1e10;
    if(x>=n+m) return 0;
    int mx=dp(x+1, clck);
    mx=max(dp(x+1, clck+table[x].first.first)+table[x].second,mx);
    return memo[{x,clck}]=mx;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    table.resize(n);
    for (int i = 0; i < n; i++) { cin >> table[i].first.first >> table[i].first.second >> table[i].second; table[i].second=-table[i].second;}
    cin >> m;
    table.resize(n+m);
    for (int i = 0; i < m; i++) { cin >> table[i+n].first.first >> table[i+n].first.second >> table[i+n].second;  table[i+n].first.first=-table[i+n].first.first; }
    sort(table.begin(),table.end(),comp);
    cout << dp(0,0) << "\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...