Submission #1222807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222807		Tenis0206	Cloud Computing (CEOI18_clo)	C++20	100 / 100	153 ms	1480 KiB

clo

#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;
}

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10