제출 #1192573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192573		Nelt	Cloud Computing (CEOI18_clo)	C++20	100 / 100	897 ms	2336 KiB

clo

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
const ll MAX = 2005 * 50;
ll dp[MAX], ndp[MAX];
void solve()
{
    ll n;
    cin >> n;
    vector<array<ll, 4>> a;
    while (n--)
    {
        ll c, f, v;
        cin >> c >> f >> v;
        a.push_back({f, 1, c, v});
    }
    cin >> n;
    while (n--)
    {
        ll c, f, v;
        cin >> c >> f >> v;
        a.push_back({f, 0, c, v});
    }
    sort(a.begin(), a.end(), greater());
    for (ll i = 1; i < MAX; i++) dp[i] = -1e18;
    for (auto [_, tp, c, v] : a)
    {
        for (ll i = 0; i < MAX; i++) ndp[i] = -1e18;
        for (ll i = 0; i < MAX; i++)
            if (i + (tp == 1 ? c : -c) < MAX and i + (tp == 1 ? c : -c) >= 0) 
                ndp[i + (tp == 1 ? c : -c)] = max(ndp[i + (tp == 1 ? c : -c)], dp[i] + (tp == 1 ? -v : v));
        for (ll i = 0; i < MAX; i++) dp[i] = max(dp[i], ndp[i]);
    }
    ll ans = 0;
    for (ll i = 0; i < MAX; i++) ans = max(ans, dp[i]);
    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll cs = 1; cs <= t; cs++)
        solve();
    // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

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