제출 #1338814

#제출 시각아이디문제언어결과실행 시간메모리
1338814ninstroyerCloud Computing (CEOI18_clo)C++20
100 / 100
466 ms2188 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long

const ll cx = 1e5+5, inf = 1e18;

ll n,m,total,dp[2][cx];
vector<tuple<ll,ll,ll>> items;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        ll c,f,v; cin>>c>>f>>v;
        items.push_back({f,c,v});
        total += c;
    }
    cin>>m;
    for(int i = 1; i <= m; i++)
    {
        ll c,f,v; cin>>c>>f>>v;
        items.push_back({f,-c,-v});
    }
    sort(items.begin(),items.end(),greater<tuple<ll,ll,ll>>());
    for(int i = 0; i < 2; i++) for(int j = 1; j <= total; j++) dp[i][j]=-inf;
    for(int i = 0; i < items.size(); i++)
    {
        auto [f,c,v] = items[i];
        int cur = i&1;
        int prev = !cur;
        for(int j = 0; j <= total; j++)
        {
            dp[cur][j]=max(dp[cur][j],dp[prev][j]);
            if(j+c<=total && j+c>=0) dp[cur][j+c] = max(dp[cur][j+c],dp[prev][j]-v);

        }
    }
    ll res = 0;
    for(int i = 0; i <= total; i++) res = max(res,dp[(items.size()-1)&1][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...