Submission #861420

#	Time	Username	Problem	Language	Result	Execution time	Memory
861420		overwatch9	Cloud Computing (CEOI18_clo)	C++17	54 / 100	553 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;
}
vector <vector <vector <ll>>> dp;
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 = 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 <= 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() {
    // freopen("in.txt", "r", stdin);
	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(), comp);

	dp = vector <vector <vector <ll>>> (n+1, vector <vector <ll>> (101, vector <ll> (m+1, -1e16)));

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

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