Submission #573011

#	Time	Username	Problem	Language	Result	Execution time	Memory
573011		urosk	Cloud Computing (CEOI18_clo)	C++14	100 / 100	1686 ms	1728 KiB

clo

//https://oj.uz/problem/view/CEOI18_clo
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;

#define maxn 2005
#define maxc 55
#define mx 100000
ll n,m;
struct komp{
    ll f,tip,c,v;
};
bool cmp(komp a,komp b){
    if(a.f==b.f) return a.tip<b.tip;
    return a.f<b.f;
}
ll dp[maxc*maxn];
int main(){
	daj_mi_malo_vremena
    vector<komp> a;
    cin >> n;
    for(ll i = 1;i<=n;i++){
        ll f,c,v;
        cin >> c >> f >> v;
        a.pb({f,1,c,v});
    }
    cin >> m;
    for(ll i = 1;i<=m;i++){
        ll f,c,v;
        cin >> c >> f >> v;
        a.pb({f,0,c,v});
    }
    for(ll i = 0;i<=mx;i++) dp[i] = 0;
    sort(all(a),cmp);
    for(komp p : a){
        ll c = p.c;
        ll v = p.v;
        cerr<<c<< " "<<v<<endl;
        if(p.tip==1){
            for(ll i = c;i<=mx;i++){
                dp[i-c] = max(dp[i-c],dp[i] - v);
            }
        }else{
            for(ll i = mx;i>=c;i--){
                dp[i] = max(dp[i],dp[i-c] + v);
            }
        }
        for(ll i = 1;i<=mx;i++) dp[i] = max(dp[i],dp[i-1]);
    }
    cout<<dp[0]<<endl;
	return 0;
}
/*
4
4 2200 700
2 1800 10
20 2550 9999
4 2000 750
3
1 1500 300
6 1900 1500
3 2400 4550
ans: 350
*/

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