제출 #861415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
861415		overwatch9	Cloud Computing (CEOI18_clo)	C++17	18 / 100	72 ms	262144 KiB

clo

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int n, m;
struct computer {
	int cores = 0;
	ll speed = 0, money = 0;
};
vector <computer> sellers, buyers;
bool comp(computer a, computer b) {
	return a.speed < b.speed;
}
bool comp2(computer a, computer b) {
	if (a.speed == b.speed)
		return a.money < b.money;
	return a.speed < b.speed;
}
const int maxcore = 50 + 1;
const int maxn = 2000 + 1;
const int maxm = 2000 + 1;
ll dp[maxn][maxcore][maxm];
ll solve(int i, int rem, int j) {
	if (j == 0)
        return 0;
    if (dp[i][rem][j] != -1e16)
        return dp[i][rem][j];
    ll ans = -1e15;
    ans = max(ans, solve(i, rem, j-1));
    // buyers buy from cores bought by sellers
    if (rem >= buyers[j].cores) {
        if (sellers[i+1].speed >= buyers[j].speed)
            ans = max(ans, solve(i, rem - buyers[j].cores, j-1) + buyers[j].money);
    }
    // sellers buy cores
    if (i >= 1 && rem + sellers[i].cores <= 50) {
        ans = max(ans, solve(i-1, rem, j));
        ans = max(ans, solve(i-1, rem + sellers[i].cores, j) - sellers[i].money);
    }
    dp[i][rem][j] = ans;
    return ans;
}
int main() {
	cin >> n;
	sellers.resize(n+1);
	for (int i = 1; i <= n; i++)
		cin >> sellers[i].cores >> sellers[i].speed >> sellers[i].money;
	cin >> m;
	buyers.resize(m+1);
	for (int i = 1; i <= m; i++)
		cin >> buyers[i].cores >> buyers[i].speed >> buyers[i].money;
	sort(sellers.begin(), sellers.end(), comp);
	sort(buyers.begin(), buyers.end(), comp2);

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j < maxcore; j++) {
			for (int k = 0; k <= m; k++) {
                dp[i][j][k] = -1e16;
			}
		}
	}

	cout << max((ll)0, solve(n, 0, m)) << '\n';
}

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