제출 #736973

#제출 시각아이디문제언어결과실행 시간메모리
736973studyCloud Computing (CEOI18_clo)C++17
100 / 100
431 ms1368 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...