Submission #906748

#	Time	Username	Problem	Language	Result	Execution time	Memory
906748		vjudge1	Cloud Computing (CEOI18_clo)	C++17	100 / 100	867 ms	3156 KiB

clo

#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 3e5 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct Data {
	int cor;
	int frq;
	int val;
	Data(int cor_ = 0, int frq_ = 0, int val_ = 0) : cor(cor_), frq(frq_), val(val_) {}
};
ll dp[MAXN]; // dp1(i) = max gain you can get with i cores
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<Data> a(n);
	for (int i = 0; i < n; i++){
		int cor, frq, val;
		cin >> cor >> frq >> val;
		a[i] = Data(cor, frq, -val);
	}
	int m; cin >> m;
	for (int i = 0; i < m; i++){
		int cor, frq, val;
		cin >> cor >> frq >> val;
		a.pb(Data(cor, frq, val));
	}
	sort(all(a), [](Data lhs, Data rhs){
		if (lhs.frq == rhs.frq) return lhs.val < rhs.val;
		return lhs.frq > rhs.frq;
	});
	for (int i = 0; i < MAXN; i++){
		dp[i] = -1e15;
	}
	dp[0] = 0;
	for (auto it : a){
		if (it.val < 0){
			for (int i = MAXN - 1; i >= it.cor; i--){
				ckmax(dp[i], dp[i - it.cor] + it.val);
			}
		}
		else if (it.val > 0){
			for (int i = 0; i + it.cor < MAXN; i++){
				ckmax(dp[i], dp[i + it.cor] + it.val);
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i < MAXN; i++){
		ans = max(ans, dp[i]);
	}
	cout << ans << endl;
}

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