Submission #444705

#	Time	Username	Problem	Language	Result	Execution time	Memory
444705		definitelynotmee	Cloud Computing (CEOI18_clo)	C++98	100 / 100	707 ms	1228 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;
    vector<specs> comp(n);
    for(int i = 0; i < n; i++)
        cin >> comp[i].c >> comp[i].f >> comp[i].v;

    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(n*50+1,-INFL);
    dp[0] = 0;
    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 = n*50; j >= comp[ptr].c; j--){
                dp[j] = max(dp[j],dp[j-comp[ptr].c] -comp[ptr].v);
            }
            ptr++;
        }
        //cout << i << ":\n";
        for(int j = 0; j <= n*50-order[i].c; j++){
            dp[j] = max(dp[j], dp[j+order[i].c] + order[i].v);
            //cout << (dp[j] < -INF ? "-INF" : to_string(dp[j])) << ' ';
            resp = max(resp,dp[j]);
        }
        //cout << '\n';
    }
    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