Submission #119971

#	Time	Username	Problem	Language	Result	Execution time	Memory
119971		raghav0307	Cloud Computing (CEOI18_clo)	C++14	0 / 100	47 ms	2176 KiB

clo

/*raghav0307 - Raghav Gupta*/

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
#define int ll

struct Item{
	int c, f, v, prod;
	Item (int cc, int ff, int vv, int type) : 
			c(cc), f(ff), v(vv), prod(type) {}
};

bool custom(Item a, Item b){
	if(a.f < b.f)
		return false;
	if(a.f > b.f)
		return true;
	if(a.prod == 1)
		return true;
	return false;
}

vector<Item> v;

const int MAXN = 2e3 + 5;
const int MAXC = 50;
const int inf = 1e15;

int dp[MAXN*MAXC], dp2[MAXN*MAXC];

// int memo[MAXN + 500][800];

// int dp(int pos, int left){
// 	if(pos == v.size())	return 0;
// 	if(memo[pos][left] != -1)	return memo[pos][left];
// 	if(v[pos].prod == 1){
// 		if(left + v[pos].c >= 800)	memo[pos][left] = dp(pos + 1, left);
// 		return memo[pos][left] = max( dp(pos+1, left + v[pos].c) - v[pos].v, dp(pos+1, left)); 
// 	}
// 	else if(v[pos].prod == 2){
// 		if(v[pos].c <= left) return memo[pos][left] =  max(dp(pos + 1, left - v[pos].c) + v[pos].v, dp(pos +1 , left));
// 		return memo[pos][left] = dp(pos + 1, left);
// 	}
// }


signed main(){
	fast_io();
	// memset(memo, -1, sizeof(memo));
	int n;	cin >> n;
	for(int i = 0; i < n; i++){
		int c, f, vv;
		cin >> c >> f >> vv;
		v.push_back(Item(c, f, vv, 1));
	}
	int m;	cin >> m;
	for(int i = 0; i < m; i++){
		int c, f, vv;
		cin >> c >> f >> vv;
		v.push_back(Item(c, f, vv, 2));
	}
	sort(v.begin(), v.end(), custom);
	// for(auto x : v){
	// 	cout << x.c << " " << x.f << " " << x.v << " " << x.prod << "\n";
	// }
	for(int i = 0; i < MAXN*MAXC; i++)	dp[i] = 0;
	if(v.back().prod == 2){
		for(int i = v.back().c; i <= MAXN*MAXC; i++){
			dp[i] = v.back().v;
		}
	}
	// for(int i = 0; i < 25; i++){
	// 	cout << dp[i] << " ";
	// }cout << "\n";
	for(int i = n+m-2; i >= 0; i--){
		for(int j = MAXN*MAXC-1; j >= 0; j--){
			if(v[i].prod == 1 and j + v[i].c < MAXN*MAXC){
				dp2[j] = max(dp[j + v[i].c] - v[i].v, dp2[j]);
				dp2[j] = max(dp2[j], dp[j]);
			}
			else if(v[i].prod == 2 and j >= v[i].c){
				dp2[j] = max(dp[j - v[i].c] + v[i].v, dp2[j]);
				dp2[j] = max(dp2[j], dp[j]);
			}
		}
		for(int i = 0; i < MAXC*MAXN; i++)
			dp[i] = dp2[i];
		// for(int i = 0; i < 25; i++){
		// 	cout << dp[i] << " ";
		// }cout << "\n";
	}
	cout << max(dp[0], 0ll) << "\n";
	return 0;
}

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