Submission #702870

#TimeUsernameProblemLanguageResultExecution timeMemory
702870VladPislaruCloud Computing (CEOI18_clo)C++17
0 / 100
35 ms696 KiB
#include <bits/stdc++.h>

using namespace std;

int n, m;

struct Elem {
    int cores, frecv;
    long long value;
    bool operator < (const Elem A) const {
        return frecv > A.frecv;
    }
};

Elem a[4005];
long long dp1[100005], dp2[100005];

int main()
{
    cin >> n;
    int sum_c = 0;
    for (int i = 1; i <= n; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        a[i] = {c, f, -v};
        sum_c += c;
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        a[n + i] = {-c, f, v};
    }
    n = m + n;
    sort(a + 1, a + n + 1);
    /**
    for (int i = 1; i <= n; i++)
        cout << a[i].cores << " " << a[i].frecv << " " << a[i].value << "\n";*/
    for (int i = 0; i <= sum_c; i++)
        dp1[i] = LLONG_MIN, dp2[i] = LLONG_MIN;
    for (int i = 1; i <= n; i++) {
        if (a[i].cores > 0) {
            for (int j = sum_c; j >= 0; j--)
                if (dp1[j] > LLONG_MIN && j + a[i].cores >= 0) {
                    dp2[j + a[i].cores] = max({dp2[j + a[i].cores], dp1[j] + a[i].value, dp1[j + a[i].cores]});
                }
            dp2[a[i].cores] = max({dp2[a[i].cores], a[i].value,  dp1[a[i].cores]});
        }
        else {
            for (int j = 0; j <= sum_c; j++)
                if (dp1[j] > LLONG_MIN && j + a[i].cores >= 0) {
                    dp2[j + a[i].cores] = max({dp2[j + a[i].cores], dp1[j] + a[i].value,  dp1[j + a[i].cores]});
                }
            dp2[a[i].cores] = max({dp2[a[i].cores], a[i].value,  dp1[a[i].cores]});
        }
        /**
        if (i == 6)
            cout << a[i].value << " " << dp2[2] << "!!!!!\n\n";
        for (int j = 0; j <= sum_c; j++)
            cout << dp2[j] << " ";
        cout << "\n";
        */
        for (int j = 0; j <= sum_c; j++)
            dp1[j] = dp2[j], dp2[j] = LLONG_MIN;



    }
    long long ans = 0;
    for (int i = 0; i <= sum_c; i++)
        ans = max(ans, dp1[i]);
    cout << ans << "\n";
    return 0;
}
#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...