제출 #1222807

#제출 시각아이디문제언어결과실행 시간메모리
1222807Tenis0206Cloud Computing (CEOI18_clo)C++20
100 / 100
153 ms1480 KiB
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int vmax = 1e5;
const int oo = LLONG_MAX;

int n, m;
vector<pair<pair<int,int>,pair<int,int>>> l;

int dp[vmax + 5];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // homf
    cin>>n;
    int sum_st = 0, sum_dr = 0;
    for(int i=1;i<=n;i++)
    {
        int c, f, v;
        cin>>c>>f>>v;
        l.push_back({{f, 1}, {v, c}});
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int c, f, v;
        cin>>c>>f>>v;
        l.push_back({{f, 0}, {v, c}});
        sum_dr += c;
    }
    sort(l.begin(), l.end(), greater<pair<pair<int,int>,pair<int,int>>>());
    for(int i=1;i<=vmax;i++)
    {
        dp[i] = -oo;
    }
    for(auto it : l)
    {
        int tip = it.first.second;
        int cst = it.second.first;
        int val = it.second.second;
        if(tip == 1)
        {
            for(int i=min(sum_st, sum_dr + 50);i>=0;i--)
            {
                if(dp[i] == -oo)
                {
                    continue;
                }
                dp[i + val] = max(dp[i + val], dp[i] - cst);
            }
            sum_st += val;
        }
        else
        {
            for(int i=val;i<=min(sum_st, sum_dr + 50);i++)
            {
                if(dp[i] == -oo)
                {
                    continue;
                }
                dp[i - val] = max(dp[i - val], dp[i] + cst);
            }
            sum_dr -= val;
        }
    }
    int rez = -oo;
    for(int i=0;i<=vmax;i++)
    {
        rez = max(rez, dp[i]);
    }
    cout<<rez<<'\n';
    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...