Submission #1067359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067359		roimu	Cloud Computing (CEOI18_clo)	C++14	100 / 100	283 ms	1372 KiB

clo

//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:
	int core;
	int type;
	int cost;
	int cnt;

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

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

	return y.core < x.core;
}

int main() {
	int n; cin >> n;
	vector<pc> a;
	for (int i = 0; i < n; i++) {
		int 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++) {
		int cnt, core, val;
		cin >> cnt >> core >> val;
		a.emplace_back(core, 1, val, cnt);
	}

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

	LL e = -INF2;

	int uba = 50 * 2000;
	vector<LL> dp(uba+10, e); dp[0] = 0;
	n = a.size();
	
	int ub = 0;
	for (int i = 0; i < n; i++) {
		int cnt = a[i].cnt;
		int val = a[i].cost;
		//在庫追加チャンス
		
		if (a[i].type == 0) {
			ub += cnt;
			for (int j = min(ub,uba); 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<=min(ub,uba); 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;
}

/*

*/

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