Submission #74081

#TimeUsernameProblemLanguageResultExecution timeMemory
74081haitunCloud Computing (CEOI18_clo)C++14
100 / 100
908 ms3448 KiB
#include <bits/stdc++.h>
//#include "functions.h"
#define FOR(x,y) for(int x = 0; x < y; x++)
#define ALLR(x) x.begin(),x.end()
#define con continue
#define ll long long
#define LINF LLONG_MAX
#define INF INT_MAX
#define pii pair<int,int>
#define vi vector <int>
#define pb push_back
#define F first
#define S second
#define len(x) x.length()
#define sz(x) x.size()
#define SEE(v)	for(auto x : v)	cout << x << " "; cout << endl;
#define buy 1
#define sell 0
using namespace std;
int main(){
	vector <pair<pair<ll,ll>, pair<ll, ll> > > com;
	ll n;
	cin >> n;
	FOR(j, n)
	{
		ll x,y,z;
		cin >> x >> y >> z;
		com.pb(make_pair(make_pair(y, 1), make_pair(x, z)));
	}
	ll m;
	cin >> m;
	FOR(j, m)
	{
		ll x,y,z;
		cin >> x >> y >> z;
		com.pb(make_pair(make_pair(y, 0), make_pair(x, z)));
	}
	
	sort(ALLR(com));
	reverse(ALLR(com));
	
	ll dp[2][111115]; //dp[i][j], 0 is previous situation, j is cores lefted
	FOR(j, 111115)	dp[0][j] = dp[1][j] = -LINF;
	
	dp[1][0] = 0; //1 is "previous" && we start with 0 core
	
	FOR(j, n + m)
	{
		ll cur = j % 2, prev = ((cur == 0) ? 1 : 0); //prev points to previous situation
		//cout << cur << " " << prev << endl;
		ll type = com[j].F.S, core = com[j].S.F, cost = com[j].S.S;
		
		//cout << f << " " << type << " " << core << " " << cost << endl;
		
		//set current situation to -INF
		//check all posibble # of cores
		//if have cores, then process buy || sell
		
		FOR(k, 111111)	dp[cur][k] = -LINF;
		
		FOR(k, 111111)
		{
			if(dp[prev][k] > -LINF)
			{
				ll p = dp[prev][k];
				if(dp[cur][k] < p)	dp[cur][k] = p;
				if(type == buy)
				{
					if(dp[cur][k + core] < p - cost)	dp[cur][k + core] = p - cost;
				}
				else// if(type == sell)
				{
					if(k >= core)	if(dp[cur][k - core] < p + cost)	dp[cur][k - core] = p + cost;
				}
			}
		}
	}
	
	ll ans = 0;
	
	FOR(j, 111111)
	{
		ans = max(ans, dp[(n + m - 1) % 2][j]);
	}
	cout << ans;
	
}
#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...