oj.uz

Submission #74081

# Submission time Handle Problem Language Result Execution time Memory
74081 2018-08-30T03:36:14 Z haitun Cloud Computing (CEOI18_clo) C++14
100 / 100
 908 ms 3448 KB 
#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;
	
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Correct 4 ms 2204 KB Output is correct
3 Correct 17 ms 2204 KB Output is correct
4 Correct 30 ms 2204 KB Output is correct
5 Correct 251 ms 2260 KB Output is correct
6 Correct 256 ms 2348 KB Output is correct
7 Correct 302 ms 2348 KB Output is correct
8 Correct 308 ms 2452 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2452 KB Output is correct
2 Correct 5 ms 2452 KB Output is correct
3 Correct 17 ms 2452 KB Output is correct
4 Correct 22 ms 2452 KB Output is correct
5 Correct 131 ms 2452 KB Output is correct
6 Correct 125 ms 2452 KB Output is correct
7 Correct 323 ms 2572 KB Output is correct
8 Correct 262 ms 2776 KB Output is correct
9 Correct 355 ms 2776 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2776 KB Output is correct
2 Correct 7 ms 2776 KB Output is correct
3 Correct 25 ms 2776 KB Output is correct
4 Correct 26 ms 2776 KB Output is correct
5 Correct 50 ms 2776 KB Output is correct
6 Correct 49 ms 2776 KB Output is correct
7 Correct 70 ms 2776 KB Output is correct
8 Correct 72 ms 2776 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2776 KB Output is correct
2 Correct 5 ms 2776 KB Output is correct
3 Correct 210 ms 2776 KB Output is correct
4 Correct 238 ms 2820 KB Output is correct
5 Correct 656 ms 2820 KB Output is correct
6 Correct 813 ms 2948 KB Output is correct
7 Correct 908 ms 2948 KB Output is correct
8 Correct 799 ms 2960 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2960 KB Output is correct
2 Correct 25 ms 2960 KB Output is correct
3 Correct 122 ms 2960 KB Output is correct
4 Correct 257 ms 2960 KB Output is correct
5 Correct 715 ms 3004 KB Output is correct
6 Correct 802 ms 3004 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Correct 4 ms 2204 KB Output is correct
3 Correct 17 ms 2204 KB Output is correct
4 Correct 30 ms 2204 KB Output is correct
5 Correct 251 ms 2260 KB Output is correct
6 Correct 256 ms 2348 KB Output is correct
7 Correct 302 ms 2348 KB Output is correct
8 Correct 308 ms 2452 KB Output is correct
9 Correct 4 ms 2452 KB Output is correct
10 Correct 5 ms 2452 KB Output is correct
11 Correct 17 ms 2452 KB Output is correct
12 Correct 22 ms 2452 KB Output is correct
13 Correct 131 ms 2452 KB Output is correct
14 Correct 125 ms 2452 KB Output is correct
15 Correct 323 ms 2572 KB Output is correct
16 Correct 262 ms 2776 KB Output is correct
17 Correct 355 ms 2776 KB Output is correct
18 Correct 7 ms 2776 KB Output is correct
19 Correct 7 ms 2776 KB Output is correct
20 Correct 25 ms 2776 KB Output is correct
21 Correct 26 ms 2776 KB Output is correct
22 Correct 50 ms 2776 KB Output is correct
23 Correct 49 ms 2776 KB Output is correct
24 Correct 70 ms 2776 KB Output is correct
25 Correct 72 ms 2776 KB Output is correct
26 Correct 5 ms 2776 KB Output is correct
27 Correct 5 ms 2776 KB Output is correct
28 Correct 210 ms 2776 KB Output is correct
29 Correct 238 ms 2820 KB Output is correct
30 Correct 656 ms 2820 KB Output is correct
31 Correct 813 ms 2948 KB Output is correct
32 Correct 908 ms 2948 KB Output is correct
33 Correct 799 ms 2960 KB Output is correct
34 Correct 4 ms 2960 KB Output is correct
35 Correct 25 ms 2960 KB Output is correct
36 Correct 122 ms 2960 KB Output is correct
37 Correct 257 ms 2960 KB Output is correct
38 Correct 715 ms 3004 KB Output is correct
39 Correct 802 ms 3004 KB Output is correct
40 Correct 149 ms 3004 KB Output is correct
41 Correct 298 ms 3004 KB Output is correct
42 Correct 371 ms 3064 KB Output is correct
43 Correct 642 ms 3212 KB Output is correct
44 Correct 625 ms 3212 KB Output is correct
45 Correct 634 ms 3356 KB Output is correct
46 Correct 264 ms 3448 KB Output is correct
47 Correct 395 ms 3448 KB Output is correct
48 Correct 385 ms 3448 KB Output is correct