Submission #1259760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259760		vuviet	Cloud Computing (CEOI18_clo)	C++20	36 / 100	8 ms	584 KiB

clo

/**
 *  __      __   __      __
 *  \ \    / /   \ \    / (_)     _____
 *   \ \  / /_   _\ \  / / _  ___|_   _|
 *    \ \/ /| | | |\ \/ / | |/ _ \ | |
 *     \  / | |_| | \  /  | |  __/ | |
 *      \/   \__,_|  \/   |_|\____||_|
 *
 *     Author:    ~Noah-kun~
 *     Created:   2025-08-17 19:00
**/

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ____VuViet__ signed main

const int maxN = 4e3 + 3;
const int maxC = 1e4 + 4;
const int inf = 1e18;

struct Deal
{
    int c, f, v;
    bool operator < (Deal o) const
    {
        if (f == o.f) return v < o.v;
        return f > o.f;
    }
} deals[maxN];
int dp[maxC], sumc = 0, n, m;

void ReadData()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        int c, f, v;
        cin >> c >> f >> v;
        deals[i] = {c, f, -v};
        sumc += c;
    }
    cin >> m;
    for (int i = n + 1; i <= n + m; ++i)
    {
        int c, f, v;
        cin >> c >> f >> v;
        deals[i] = {-c, f, v};
    }
}

bool check(int pos)
{
    return pos >= 0 && pos <= sumc;
}

void Solve()
{
    for (int j = 0; j <= sumc; ++j)
        dp[j] = -inf;
    dp[0] = 0;
    sort(deals + 1, deals + 1 + n + m);
    for (int i = 1; i <= n + m; ++i)
    {
        auto [c, f, v] = deals[i];
        int j = (c > 0 ? sumc : 0);
        int en = (c > 0 ? c : sumc + c);
        int step = (c > 0 ? -1 : 1);
        while ((c > 0 ? j >= en : j <= en))
        {
            int p = j - c;
            if (check(j - c) && dp[j - c] != -inf)
                dp[j] = max(dp[j], dp[j - c] + v);
            j += step;
        }
    }
    int ans = 0;
    for (int j = 0; j <= sumc; ++j)
        ans = max(ans, dp[j]);
    cout << ans;
}

____VuViet__()
{
    ReadData();
    Solve();
    return 0;
}

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