Submission #1060106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060106		Piokemon	Cloud Computing (CEOI18_clo)	C++17	36 / 100	141 ms	2136 KiB

clo

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int N = 2000;
ll kompy[N+9][3]; // ile f koszt
ll osoby[N+9][3];
ll cheapk[N*50+9];
ll buyer[N*50+9];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin >> n;
    bool c1=1,f1=1;
    for (int x=1;x<=n;x++){
        cin >> kompy[x][0] >> kompy[x][1] >> kompy[x][2];
        if (kompy[x][0]>1)c1=0;
        if (kompy[x][1]>1)f1=0;
    }
    cin >> m;
    for (int x=1;x<=m;x++){
        cin >> osoby[x][0] >> osoby[x][1] >> osoby[x][2];
        if (osoby[x][0]>1)c1=0;
        if (osoby[x][1]>1)f1=0;
    }
    if (c1){
        vector<pair<ll,ll>> kup;
        priority_queue<ll> mozl;
        vector<pair<ll,ll>> oso;
        for (int x=1;x<=n;x++)kup.push_back({kompy[x][1],kompy[x][2]});
        kup.push_back({-1,1e9});
        sort(kup.begin(),kup.end(),greater<pair<ll,ll>>());
        for (int x=1;x<=m;x++)oso.push_back({osoby[x][1],osoby[x][2]});
        sort(oso.begin(),oso.end());
        mozl.push(-2e9);
        int p=0;
        ll odp=0;
        for (int x=m-1;x>=0;x--){
            while(kup[p].first>=oso[x].first){
                mozl.push(-kup[p].second);
                p++;
            }
            if (-mozl.top()<oso[x].second){
                odp += oso[x].second+mozl.top(); mozl.pop();
                mozl.push(-oso[x].second);
            }
        }
        cout << odp << '\n';
        return 0;
    }
    if (f1){
        for (int x=0;x<=max(n,m)*50;x++){
            cheapk[x]=(ll)1e18;
            buyer[x]=(ll)-1e18;
        }
        buyer[0]=0; cheapk[0]=0;
        for (int x=1;x<=n;x++){
            for (int y=50*x;y>=kompy[x][0];y--){
                cheapk[y]=min(cheapk[y],cheapk[y-kompy[x][0]]+kompy[x][2]);
            }
        }
        for (int x=1;x<=m;x++){
            for (int y=50*x;y>=osoby[x][0];y--){
                buyer[y]=max(buyer[y],buyer[y-osoby[x][0]]+osoby[x][2]);
            }
        }
        ll odp=0;
        for (int x=50*n;x>=1;x--)cheapk[x-1]=min(cheapk[x-1],cheapk[x]);
        for (int x=0;x<=50*min(n,m);x++){
            buyer[x+1]=max(buyer[x+1],buyer[x]);
            odp=max(odp,buyer[x]-cheapk[x]);
        }
        cout << odp << '\n';
        return 0;
    }
    return 0;
}

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