Submission #444706

#	Time	Username	Problem	Language	Result	Execution time	Memory
444706		definitelynotmee	Cloud Computing (CEOI18_clo)	C++98	100 / 100	595 ms	1100 KiB

clo

#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6+1;

struct specs{
    ll c, f, v;
};

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    ll corecount = 0;
    vector<specs> comp(n);
    for(int i = 0; i < n; i++)
        cin >> comp[i].c >> comp[i].f >> comp[i].v;
    for(int i = 0; i < n; i++)
        corecount += comp[i].c;

    int m;
    cin >> m;
    vector<specs> order(m);

    for(int i = 0; i < m; i++)
        cin >> order[i].c >> order[i].f >> order[i].v;
    
    sort(comp.begin(), comp.end(),[&](specs a, specs b){
        return a.f > b.f;
    });
    sort(order.begin(), order.end(),[&](specs a, specs b){
        return a.f > b.f;
    });

    vector<ll> dp(corecount+1,-INFL);
    dp[0] = 0;
    // dp[i] = best value of configurations of orders that have i cores to spare

    
    int ptr = 0;
    ll resp = 0;
    for(int i = 0; i < m; i++){
        while(ptr < n && comp[ptr].f >= order[i].f){
            for(int j = corecount; j >= comp[ptr].c; j--){
                dp[j] = max(dp[j],dp[j-comp[ptr].c] -comp[ptr].v);
            }
            ptr++;
        }
        for(int j = 0; j <= corecount-order[i].c; j++){
            dp[j] = max(dp[j], dp[j+order[i].c] + order[i].v);
        }
    }
    for(int i = 0; i <= corecount; i++)
        resp = max(resp,dp[i]);
    cout << resp << '\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