Submission #1322382

#TimeUsernameProblemLanguageResultExecution timeMemory
1322382sjoxuzchloeCloud Computing (CEOI18_clo)C++20
36 / 100
289 ms1196 KiB

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;
typedef long long ll;

struct Computers {
    int c;ll f, p;
    
    bool operator<(const Computers &other) const {
        return f > other.f;
    }
};

struct Order {
    int c; ll f, p;
    bool operator<(const Order& other) const {
        return f > other.f;
    }
};

int main()
{
    int n;
    cin >> n;
    vector<Computers> cores(n);
    int coresnum = 0;
    for (int i = 0; i < n; i++) {
        cin >> cores[i].c >> cores[i].f >> cores[i].p;
        coresnum += cores[i].c;
    }
    sort(cores.begin(), cores.end());
    int m;
    cin >> m;
    vector<Order> orders(m);
    for (int i = 0; i < m; i++) {
        cin >> orders[i].c>>orders[i].f>>orders[i].p;
    }
    sort(orders.begin(), orders.end());
    vector<ll> dp(coresnum + 1, INT_MIN);
    dp[0] = 0;
    int i = 0, j = 0;
    int maxi = 0;
    while (i < n || j < m) {
        if (j == m || i < n && cores[i].f >= orders[j].f) {
            for (int w = coresnum-cores[i].c; w >= 0; w--) {
                if(dp[w]!=INT_MIN)
                dp[w+cores[i].c] = max(dp[w+cores[i].c], dp[w] - cores[i].p);
            }
            maxi += cores[i].c;
            i++;
        }
        else {
            for (int w = orders[j].c; w <= maxi; w++) {
                if(dp[w]!=INT_MIN)
                dp[w-orders[j].c] = max(dp[w]+orders[j].p, dp[w - orders[j].c]);
            }
            j++;
        }
    }
    ll ma = 0;
    for (ll v : dp) {
        ma = max(ma, v);
    }
    cout << ma << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...