제출 #1067331

#제출 시각아이디문제언어결과실행 시간메모리
1067331roimuCloud Computing (CEOI18_clo)C++14
0 / 100
7 ms1116 KiB

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>
#include <unordered_map>
#include <random>


using namespace std;

typedef long long LL;

const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

class pc {
public:
	LL core;
	LL type;
	LL cost;
	LL cnt;

	pc(LL c, LL t, LL v_,LL x_) {
		core = c;
		type = t;
		cost = v_;
		cnt = x_;
	}
};

bool cmp(const pc &x, const pc &y) {
	if (x.core > y.core) {
		return true;
	}
	else if (x.core == y.core) {
		if (x.type < y.type) {
			return true;
		}
	}

	return false;
}

int main() {
	int n; cin >> n;
	vector<pc> a;
	for (int i = 0; i < n; i++) {
		LL cnt, core, val;
		cin >> cnt >> core >> val;
		a.emplace_back(core, 0, val, cnt);
	}
	int m; cin >> m;
	for (int i = 0; i < m; i++) {
		LL cnt, core, val;
		cin >> cnt >> core >> val;
		a.emplace_back(core, 1, val, cnt);
	}

	sort(a.begin(), a.end(),cmp);

	LL e = -INF2;

	vector<LL> dp(11000, e); dp[0] = 0;
	n = a.size();
	for (int i = 0; i < n; i++) {
		LL cnt = a[i].cnt;
		LL val = a[i].cost;
		//在庫追加チャンス
		LL ub = (i + 1) * 50;
		if (a[i].type == 0) {
			for (int j = ub; j-cnt >= 0; j--) {
				if (dp[j - cnt] != e) {
					dp[j] = max(dp[j], dp[j - cnt] - val);
				}
			}
		}
		//客に売る
		if (a[i].type == 1) {
			for (int j = 0; j+cnt<=ub; j++) {
				if (dp[j + cnt] != e) {
					dp[j] = max(dp[j], dp[j + cnt] + val);
				}
			}
		}
	}

	cout << *max_element(dp.begin(), dp.end()) << endl;
	return 0;
}

/*

*/
#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...