제출 #747609

#제출 시각아이디문제언어결과실행 시간메모리
747609bgnbvnbvCloud Computing (CEOI18_clo)C++14
100 / 100
371 ms1284 KiB
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n;
struct qq
{
    ll c,f,v;
    bool operator<(const qq&o)
    {
        if(f==o.f) return c>o.c;
        return f>o.f;
    }
}p[maxN];
ll m;
ll dp[maxN];
ll ans=0;
void solve()
{
    cin >> n;
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        cin >> p[i].c >> p[i].f >> p[i].v;
        sum+=p[i].c;
        p[i].v*=-1;
    }
    cin >> m;
    for(int i=n+1;i<=n+m;i++)
    {
        cin >>p[i].c >> p[i].f >> p[i].v;
        p[i].c*=-1;
    }
    sort(p+1,p+m+n+1);
    for(int i=0;i<=sum;i++) dp[i]=-inf;
    dp[0]=0;
    for(int i=1;i<=m+n;i++)
    {
        //cout << p[i].c <<' '<<p[i].f <<' '<<p[i].v<<'\n';
        if(p[i].c<0)
        {
            for(int j=0;j<=sum+p[i].c;j++)
            {
                dp[j]=max(dp[j],dp[j-p[i].c]+p[i].v);
            }
        }
        else
        {
            for(int j=sum;j>=p[i].c;j--)
            {
                dp[j]=max(dp[j],dp[j-p[i].c]+p[i].v);
            }
        }
    }
    for(int j=0;j<=sum;j++) ans=max(ans,dp[j]);
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}
#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...