Submission #1254292

#TimeUsernameProblemLanguageResultExecution timeMemory
1254292quan606303Cloud Computing (CEOI18_clo)C++20
100 / 100
264 ms1560 KiB
/*
 * @Author: RMQuan 
 * @Date: 2025-08-07 03:43:01 
 * @Last Modified by: RMQuan
 * @Last Modified time: 2025-08-07 04:23:30
 */
/*idea : 



*/
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define file(a) freopen(a".inp","r",stdin); freopen(a".out","w",stdout);
using namespace std;
const int MOD=1e9+7;
const int inf=1e18;
struct node
{
    int c,f,cost,type;
};
bool cmp(node x,node y)
{
    if (x.f==y.f)return x.type<y.type;
    return x.f>y.f;
}
int n,m;
vector<node> qh;
const int maxqh=2005*55;
int dp[maxqh];
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        int c,f,cost;
        cin>>c>>f>>cost;
        //cout<<c<<" "<<f<<" "<<cost<<" "<<0<<endl;
        qh.push_back({c,f,cost,0});
    }
    cin>>m;
    for (int i=1;i<=m;i++)
    {
        int c,f,cost;
        cin>>c>>f>>cost;
        //cout<<c<<" "<<f<<" "<<cost<<" "<<1<<endl;

        qh.push_back({c,f,cost,1});
    }
    sort(qh.begin(),qh.end(),cmp);
    for (int i=1;i<maxqh;i++)dp[i]=-inf;
    for (auto i:qh)
    {
        if (i.type==0)
        { 
            for(int j=maxqh-1;j>=i.c;j--)if (dp[j-i.c]!=-inf)dp[j]=max(dp[j],dp[j-i.c]-i.cost);
        }
        else if (i.type==1)
        {
            for (int j=i.c;j<maxqh;j++)if (dp[j]!=-inf)dp[j-i.c]=max(dp[j-i.c],dp[j]+i.cost);
        }
       // cout<<i.c<<" "<<i.f<<" "<<i.cost<<" "<<i.type<<endl;
    }
    int ans=0;
    for (int i=0;i<maxqh;i++)ans=max(ans,dp[i]);
    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...