제출 #555402

#제출 시각아이디문제언어결과실행 시간메모리
555402status_codingCloud Computing (CEOI18_clo)C++14
100 / 100
387 ms1376 KiB
#include <bits/stdc++.h>

using namespace std;

struct pos
{
    long long nr, val, cost;
    bool tip;

    pos(long long nr, long long val, long long cost, bool tip)
    {
        this->nr = nr;
        this->val = val;
        this->cost = cost;
        this->tip = tip;
    }

    bool operator<(pos b) const
    {
        if(val != b.val)
            return val > b.val;
        return tip < b.tip;
    }
};

long long n,m,ans;
vector<pos> v;

long long dp[100005];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        long long nr, val, cost;
        cin>>nr>>val>>cost;

        v.push_back(pos(nr, val, cost, 0));
    }

    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int nr, val, cost;
        cin>>nr>>val>>cost;

        v.push_back(pos(nr, val, cost, 1));
    }

    sort(v.begin(), v.end());

    for(int nr=0; nr<= 50*n; nr++)
        dp[nr] = -1e18;
    dp[0]=0;

    for(auto it : v)
    {
        if(it.tip == 0)
        {
            for(int nr=50*n; nr>=0; nr--)
                if(nr - it.nr >= 0)
                    dp[nr] = max(dp[nr], dp[nr-it.nr] - it.cost);
        }
        else
        {
            for(int nr=0; nr<= 50*n; nr++)
                if(nr + it.nr <= 50*n)
                    dp[nr] = max(dp[nr], dp[nr + it.nr] + it.cost);
        }
    }

    long long ans=0;
    for(int nr=0; nr<= 50*n; nr++)
        ans = max(ans, dp[nr]);

    cout<<ans;
    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...