Submission #482506

#	Time	Username	Problem	Language	Result	Execution time	Memory
482506		ArianKheirandish	Cloud Computing (CEOI18_clo)	C++17	100 / 100	264 ms	8316 KiB

clo

// in the name of God//

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x)	x.begin(),x.end()
#define F		first
#define S		second
#define MP		make_pair

const int maxn = 1e6 + 10;

ll dp[maxn], n, m;
pair<ll, pair<ll, ll> > a[maxn];

int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	for(int i = 1 ; i < maxn ; i ++)
		dp[i] = -1ll * ((ll)1e18);

    cin >> n;
    for(int i = 1 ; i <= n ; i ++){
        ll c, f, v;
		cin >> c >> f >> v;
        a[i] = (MP(f, MP(c, v)));
    }

  	cin >> m;
    for(int i = n + 1 ; i <= n + m; i ++){
        ll c, f, v;
		cin >> c >> f >> v;
		a[i] = MP(f,MP(-1ll * c, v));
	}
	
	n = n + m;
    sort(a + 1, a + n + 1);

	ll sum(0), ans(0);
	for(int i = n + m ; i >= 1 ; i --){
		ll c = abs(a[i].S.F);
		ll v = a[i].S.S;
        if(a[i].S.F > 0){
            for(ll j = sum ; j >= 0 ; j --)
                dp[c + j] = max(dp[c + j], dp[j] - v);

            sum = sum + c;
        }

		else
            for(int j = c ; j <= sum ; j ++)
                dp[j - c] = max(dp[j - c], dp[j] + v);
    }

	for(int i = 0 ; i < maxn ; i ++)
		ans = max(ans, dp[i]);

	cout << ans << '\n';
}

/*
	Hasbi Allah	
*/

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