제출 #1046427

#제출 시각아이디문제언어결과실행 시간메모리
1046427vjudge1Cloud Computing (CEOI18_clo)C++17
100 / 100
402 ms2312 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2000 + 5;
vector<ll> last, curr;
int n, m;
struct test{
    ll c, f, v, t;
};
vector<test> e;

bool cmp(const test &a, const test &b)
{
    return (a.f != b.f ? a.f > b.f : a.t < b.t);
}

void solve()
{
    int cores = 0;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int c, f, v;
        cin >> c >> f >> v;
        e.push_back({c, f, v, -1});
        cores += c;
    }
    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        int c, f, v;
        cin >> c >> f >> v;
        e.push_back({c, f, v, 1});
    }

    sort(e.begin(), e.end(), cmp);

    last.assign(cores + 5, -1e17);
    curr.assign(cores + 5, -1e17);
    last[0] = curr[0] = 0;

    for(const test &x : e)
    {
        curr = last;
        if(x.t == -1)
        {
            for(int i = x.c; i <= cores; i++)
                curr[i] = max(curr[i], last[i - x.c] - x.v);
        }
        else
        {
            for(int i = 0; i <= cores - x.c; i++)
                curr[i] = max(curr[i], last[i + x.c] + x.v);
        }
        last.swap(curr);
    }
    cout << *max_element(last.begin(), last.end());
}

signed main()
{
    solve();
    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...