Submission #826975

#	Time	Username	Problem	Language	Result	Execution time	Memory
826975		sentheta	Cloud Computing (CEOI18_clo)	C++17	100 / 100	270 ms	1404 KiB

clo

// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
	#define DBG 1
#else
	#include"bits/stdc++.h"
	#define DBG 0
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

#define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}







const int INF = 1e18;
const int N = 2005;
const int C = 52;

int n, m;
V<array<int,3>> ev;

// dp[x] = max profit if there is x cores to be fulfilled
int dp[N*C];


void solve(){

	
	cin >> n;
	
	rep(i,1,n+1){
		int cnt, freq, price;
		cin >> cnt >> freq >> price;
		
		ev.push_back({freq,cnt,-price});
	}
	
	cin >> m;
	rep(i,1,m+1){
		int cnt, freq, price;
		cin >> cnt >> freq >> price;
	
		ev.push_back({freq,-cnt,price});
	}
	
	sort(all(ev));
	
	
	dp[0] = 0;
	rep(i,1,N*C) dp[i] = -INF;
	
	int tot = 0;
	
	for(auto[freq,cnt,price] : ev){
		dbg(freq); dbg(cnt); dbg(price);
		
		// computers
		if(cnt > 0){
			cerr << "COMPUTER" << nl;
			cnt = abs(cnt); price = abs(price);
			rep(i,0,tot+1){
				int j = max(0LL, i-cnt);
				dp[j] = max(dp[j], dp[i]-price);
			}
		}
		// orders
		else{
			cerr << "ORDER" << nl;
			cnt = abs(cnt); price = abs(price);
			for(int i=tot; i>=0; i--){
				int j = i+cnt;
				dp[j] = max(dp[j], dp[i]+price);
			}
			tot += cnt;
		}
		
		cerr << nl;
	}
	
	int ans = dp[0];
	cout << ans << nl;
	
	
	
	
}

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