Submission #736973

#	Time	Username	Problem	Language	Result	Execution time	Memory
736973		study	Cloud Computing (CEOI18_clo)	C++17	100 / 100	431 ms	1368 KiB

clo

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

struct Obj{
    int rate,cost,nbCores;
};

const int N = 1e5+1, inf = 1e18;

int dp[N];

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
    cin >> n;
    vector<Obj> objects;
    for (int i=0; i<n; ++i){
        int nbCores,rate,cost;
        cin >> nbCores >> rate >> cost;
        objects.push_back({rate,-cost,nbCores});
    }
    int m;
    cin >> m;
    for (int i=0; i<m; ++i){
        int nbCores,rate,cost;
        cin >> nbCores >> rate >> cost;
        objects.push_back({rate,cost,nbCores});
    }
    sort(objects.begin(),objects.end(),[](const Obj& a, const Obj& b){
        if (a.rate != b.rate) return a.rate > b.rate;
        return a.cost < b.cost;
    });
    fill_n(&dp[0],N,-inf);
    dp[0] = 0;
    for (auto obj:objects){
        if (obj.cost < 0){
            for (int i=N-1-obj.nbCores; i>=0; --i){
                if (dp[i] != -inf) dp[i+obj.nbCores] = max(dp[i+obj.nbCores],dp[i]+obj.cost); 
            }
        }
        else{
            for (int i=obj.nbCores; i<N; ++i){
                if (dp[i] != -inf) dp[i-obj.nbCores] = max(dp[i-obj.nbCores],dp[i]+obj.cost);
            }
        }
    }
    int ans = 0;
    for (int i=0; i<N; ++i) ans = max(ans,dp[i]);
    cout << ans; 
	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