Submission #1310499

#TimeUsernameProblemLanguageResultExecution timeMemory
1310499bobothenubchickCloud Computing (CEOI18_clo)C++20
100 / 100
290 ms1312 KiB
# include <bits/stdc++.h>
using namespace std;

long long n,dp[100005],m,s;
struct helo
{
    long long c,f,v;
} a[2005],b[2005];
bool cmp1(helo x, helo y)
{
    return (x.f < y.f);
}
bool cmp2(helo x, helo y)
{
    return (x.f > y.f);
}

void update1(long long x, long long y)
{
    for (int i = s-x; i >= 0; i--)
    {
        if (dp[i] <= -1e18) continue;
        dp[i+x] = max(dp[i+x],dp[i]+y);
    }
}

void update2(long long x, long long y)
{
    for (int i = x; i <= s; i++)
    {
        if (dp[i] <= -1e18) continue;
        dp[i-x] = max(dp[i-x],dp[i]+y);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= 1e5; i++) dp[i] = -1e18;
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].c >> a[i].f >> a[i].v;
        s += a[i].c;
    }
    sort(a+1,a+n+1,cmp2);
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i].c >> b[i].f >> b[i].v;
    }
    sort(b+1,b+m+1,cmp2);
    int j = 1;
    for (int i = 1;  i<= m; i++)
    {
        while (j <= n and a[j].f >= b[i].f)
        {
            update1(a[j].c,-a[j].v);
            j++;
        }
        update2(b[i].c,b[i].v);
    }
    long long res = -1e18;
    for (int i =0; i <= s; i++)
    {
        res = max(res,dp[i]);
    }
    cout <<res;
}
#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...