Submission #1022689

#TimeUsernameProblemLanguageResultExecution timeMemory
1022689eysbutnoCloud Computing (CEOI18_clo)C++17
100 / 100
886 ms2200 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)

template<class T> bool smax(T &a, T b) {
    return a < b ? a = b, 1 : 0;
}
template<class T> bool smin(T &a, T b) {
    return a > b ? a = b, 1 : 0;
}
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n; cin >> n;
    vector<array<int, 3>> ord;
    // {cores_added, freq, val_added}
    int tot = 0;
    for (int i = 0; i < n; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        ord.push_back({c, f, -v});
        tot += c;
    }
    int m; cin >> m;
    for (int i = 0; i < m; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        ord.push_back({-c, f, v});
    }
    sort(all(ord), [&](auto &i, auto &j) -> bool {
        return (i[1] == j[1]) ? i[2] < j[2] : i[1] > j[1]; 
    });
    const ll INF = 1e15;
    vector<ll> dp(tot + 1, -INF);
    dp[0] = 0;
    for (auto [c, f, v] : ord) {
        vector<ll> dp_t(tot + 1, -INF);
        for (int i = 0; i <= tot; i++) {
            int nxt = i + c;
            if (nxt >= 0 && nxt <= tot && dp[i] != -INF) { 
                dp_t[nxt] = max(dp_t[nxt], dp[i] + v);
            }
            dp_t[i] = max(dp_t[i], dp[i]);
        }
        // dp = move(dp_t);
        dp = dp_t;
    }
    cout << *max_element(all(dp)) << "\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...