Submission #1132481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132481		ocasu	Cloud Computing (CEOI18_clo)	C++20	100 / 100	416 ms	2168 KiB

clo

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct Transaction {
    int cores;
    int rate;
    int price;
};

const int MAXCORES=100000;

const int inf=1e12;

signed main(){
    int n; cin>>n;
    vector<Transaction> transactions;
    for (int i=0; i<n; i++){
        Transaction trans;
        cin>>trans.cores>>trans.rate>>trans.price;
        trans.price *= -1;
        transactions.push_back(trans);
    }
    int m; cin>>m;
    for (int i=0; i<m; i++){
        Transaction trans;
        cin>>trans.cores>>trans.rate>>trans.price;
        trans.cores *= -1;
        transactions.push_back(trans);
    }
	std::sort(transactions.begin(), transactions.end(),
	          [](const Transaction &a, const Transaction &b) -> bool {
		          return a.rate != b.rate ? a.rate > b.rate : a.price < b.price;
	          });
    vector<int> dp(MAXCORES+1,-inf);
    dp[0]=0;
    for (auto trans: transactions){
        vector<int> ndp = dp;
        for (int i=0; i<=MAXCORES; i++){
            if (dp[i]!=-inf and 0<=i+trans.cores and i+trans.cores<=MAXCORES) ndp[i+trans.cores] = max(ndp[i+trans.cores], dp[i] + trans.price);
        }
        swap(dp, ndp);
    }
    cout<<*max_element(dp.begin(),dp.end())<<'\n';


}

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