Submission #1034424

#TimeUsernameProblemLanguageResultExecution timeMemory
1034424warrennCloud Computing (CEOI18_clo)C++14
100 / 100
279 ms1372 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct computer {
    int core, clock, price, type;
};
bool csortclock(computer a, computer b) {
	if(a.clock == b.clock)
		return a.type > b.type;
	else
    return a.clock < b.clock;
}

int main() {
    int n;
    cin >> n;
    computer a[n];
    int sum=0;
    vector<computer> v;
    for(int i = 0; i < n; ++i){
        cin >> a[i].core >> a[i].clock >> a[i].price, a[i].type = 0;
        sum+=a[i].core;
        v.push_back(a[i]);
    }
    int m;
    cin >> m;

    computer b[m];
    for(int i = 0; i < m; ++i){
        cin >> b[i].core >> b[i].clock >> b[i].price, b[i].type = 1;
        v.push_back(b[i]);
    }

  ll dp[sum + 1];
  for(int q=1;q<=sum;q++){
    dp[q]=-1e15;
  }
  dp[0] = 0;

	sort(v.begin(), v.end(), csortclock);
    for(int q=v.size()-1;q>=0;q--){
        computer c=v[q];
		if(c.type == 0) {
			for(int i =sum; i >= c.core; --i) {
				dp[i] = max(dp[i], dp[i - c.core] - c.price);
			}
		}
		else {
			for(int i = 0; i + c.core <=sum; ++i) {
				dp[i] = max(dp[i], dp[i + c.core] + c.price);
			}
		}
	}
	ll res = 0;
	for(int i = 0; i <= sum; ++i)
		res = max(res, dp[i]);
	cout << res << endl;
}
#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...