Submission #906377

#TimeUsernameProblemLanguageResultExecution timeMemory
906377LudisseyCloud Computing (CEOI18_clo)C++14
18 / 100
728 ms2140 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){
        if(a.second==b.second) return a.second>b.second;
        return a.first.first>b.first.first;
    }
    return a.first.second>b.first.second;
}

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; }
    n+=m;
    sort(table.begin(),table.end(),comp);
    vector<int> dp(1e5,-1e17);
    dp[0]=0;
    for (int i = 0; i < n; i++)
    {
        vector<int> new_dp;
        new_dp.assign(dp.begin(),dp.end());
        int core=table[i].first.first;
        int price=table[i].second;
        for (int j = 0; j < 1e5; j++) {
            if(j+core>0&&dp[j]>-1e17) {
                new_dp[j+core]=max(dp[j+core], dp[j]+price);
            }
        }
        dp.clear();
        dp.assign(new_dp.begin(),new_dp.end());
    }
    int mx=0;
    for (int i = 0; i < (int)dp.size(); i++) mx=max(dp[i], mx);
    cout << mx << "\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...