Submission #597269

#	Time	Username	Problem	Language	Result	Execution time	Memory
597269		leroycut	Cloud Computing (CEOI18_clo)	C++17	100 / 100	508 ms	2124 KiB

clo

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using ld = long double;
 
const ll N = 100003, mod = 1e9 + 7, inf = 1e18 + 7;

struct node
{
    int core, rate;
    ll cost;
}t;

bool cnt(node a, node b){
    if(a.rate == b.rate) return a.cost < b.cost;
    return a.rate > b.rate;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n;
    vector<node> v;

    for(int i = 0; i < n; ++i){
        cin >> t.core >> t.rate >> t.cost;
        t.cost = -t.cost;
        v.push_back(t);
    }

    cin >> m;

    for(int i = 0; i < m; ++i){
        cin >> t.core >> t.rate >> t.cost;
        t.core = -t.core;
        v.push_back(t);
    }

    sort(v.begin(), v.end(), cnt);

    // for(int i = 0; i < v.size(); ++i) cout << v[i].cost << "\n";

    vector<ll> last, dp(N, -inf);
    dp[0] = 0;

    for(auto i : v){
        last = dp;
        for(int c = 0; c < N; ++c){
            if(0 <= c - i.core && c - i.core < N && last[c - i.core] != -inf){
                dp[c] = max(dp[c], last[c - i.core] + i.cost);
            }
        }
    }
    
    ll ans = 0;
    for(int i = 0; i < N; ++i){
        ans = max(ans, dp[i]);
    }
    cout << ans;
}

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