Submission #1183664

#TimeUsernameProblemLanguageResultExecution timeMemory
1183664ivazivaCloud Computing (CEOI18_clo)C++20
100 / 100
558 ms2168 KiB
#include <bits/stdc++.h>

using namespace std;

#define MAXN 2001
#define MAXM 100001
#define int long long

int n,m;
vector<pair<int,pair<int,int>>> vec;
int dp[MAXM],dp1[MAXM];

int32_t main()
{
    cin>>n;int maks=0;
    for (int i=1;i<=n;i++) {int x,y,z;cin>>x>>y>>z;vec.push_back({y,{x,z*(-1)}});maks+=x;}
    cin>>m;
    for (int i=1;i<=m;i++) {int x,y,z;cin>>x>>y>>z;vec.push_back({y,{x*(-1),z}});}
    sort(vec.begin(),vec.end());reverse(vec.begin(),vec.end());
    dp[0]=0;dp1[0]=-LLONG_MAX;int ans=-LLONG_MAX;
    for (int i=1;i<=maks;i++) {dp[i]=-LLONG_MAX;dp1[i]=-LLONG_MAX;}
    for (int i=0;i<vec.size();i++)
    {
        for (int j=0;j<=maks;j++) dp1[j]=dp[j];
        int cores=vec[i].second.first,value=vec[i].second.second;
        for (int j=max((long long)0,cores);max(j-cores,j)<=maks;j++)
        {
            if (dp[j-cores]!=-LLONG_MAX) dp1[j]=max(dp1[j],dp[j-cores]+value);
        }
        for (int j=0;j<=maks;j++) dp[j]=dp1[j];
    }
    for (int i=0;i<=maks;i++) ans=max(ans,dp[i]);
    cout<<ans<<endl;
}
#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...