Submission #906389

#	Time	Username	Problem	Language	Result	Execution time	Memory
906389		Ludissey	Cloud Computing (CEOI18_clo)	C++14	100 / 100	1187 ms	3676 KiB

clo

#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(200001,-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 < 200001; 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;
}

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10