Submission #575968

#	Time	Username	Problem	Language	Result	Execution time	Memory
575968		teki	Cloud Computing (CEOI18_clo)	C++11	100 / 100	460 ms	2100 KiB

clo

#include <bits/stdc++.h>

typedef long long ll;

#define pb push_back
#define MS(x,y) memset((x),(y),sizeof((x)))

using namespace std;

const ll MN = 1000000007;

vector<pair<pair<ll,ll>, pair<ll,ll>>> a(4005);

int main()
{
    #if LOCAL_DEBUG
        fstream cin("in.txt");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    ll n,m;
    cin>>n;

    ll ctr = 0;

    for (ll i = 0; i<n; i++) {
        ll c,f,v;
        cin>>c>>f>>v;

        a[i] = { {-f,0} , {c,-v} };
        ctr += c;
    }

    cin>>m;

    for (ll i = 0; i<m; i++) {
        ll c,f,v;
        cin>>c>>f>>v;

        a[i+n] = { {-f,1} , {-c,v} };
    }

    a.resize(n+m);
    sort(a.begin(),a.end());

    const ll sajz = ctr+100;

    vector<ll> dp(sajz);
    for (ll i = 0; i<sajz; i++) dp[i] = -(MN*MN);
    dp[0] = 0;
    vector<ll> tempDp(sajz);

    for (ll i = 0; i<n+m; i++) {
        ll c = a[i].second.first, v = a[i].second.second;

        tempDp = dp;

        for (ll j = max(0ll,c); j<=ctr; j++) tempDp[j] = max(tempDp[j], dp[j-c]+v);

        swap(tempDp,dp);
    }

    ll res = 0;
    for (ll i = 0; i<sajz; i++) res = max(res,dp[i]);

    cout<<res<<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