Submission #1354037

#TimeUsernameProblemLanguageResultExecution timeMemory
1354037kantaponzCloud Computing (CEOI18_clo)C++20
100 / 100
143 ms1404 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int maxSum = 100001;

int n, m;
ll dp[maxSum];

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    vector<tuple<int,int,int,ll>> v; // f, c, v, type
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int c, f, vv;
        cin >> c >> f >> vv;
        v.emplace_back(f, 2, c, vv);
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int c, f, vv;
        cin >> c >> f >> vv;
        v.emplace_back(f, 1, c, vv);
    }
    sort(v.begin(), v.end(), greater<tuple<int,int,int,ll>>());
    n += m;
    dp[0] = 0;
    for (int k = 1; k < maxSum; k++) dp[k] = -1e18;
    for (int i = 0; i < n; i++) {
        auto [f, type, c, w] = v[i];
       // cout << f << " " << c << " " << w << " " << type << endl;
        if (type == 2) {
            for (int i = 1e5; i >= c; i--) dp[i] = max(dp[i], dp[i - c] - w);
        } else {
            for (int i = 0; i + c <= 1e5; i++) dp[i] = max(dp[i], dp[i + c] + w);
        }

    }
    ll ans = 0;
    for (int i = 0; i < maxSum; i++) ans = max(ans, dp[i]);
    cout << ans;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...