Submission #703913

#	Time	Username	Problem	Language	Result	Execution time	Memory
703913		finn__	Cloud Computing (CEOI18_clo)	C++17	100 / 100	662 ms	1996 KiB

clo

#include <bits/stdc++.h>
using namespace std;

struct Transaction
{
    uint64_t f;
    int64_t c, v;

    bool operator<(Transaction const &t) const
    {
        if (f == t.f)
            return v < 0 && !(t.v < 0);
        return f > t.f;
    }
};

#define N 4000
#define C 51

Transaction t[N];
int64_t dp[N * C];

int main()
{
    size_t n, l = 0;
    cin >> n;

    for (size_t i = 0; i < n; i++)
    {
        cin >> t[l].c >> t[l].f >> t[l].v;
        t[l].v = -t[l].v;
        l++;
    }

    size_t m;
    cin >> m;

    for (size_t i = 0; i < m; i++)
    {
        cin >> t[l].c >> t[l].f >> t[l].v;
        t[l].c = -t[l].c;
        l++;
    }

    sort(t, t + l);
    fill(dp + 1, dp + N * C, INT64_MIN);

    for (size_t i = 0; i < l; i++)
    {
        auto const &[f, c, v] = t[i];

        if (c < 0)
        {
            for (int64_t j = -c; j < N * C; j++)
                if (dp[j] != INT64_MIN)
                    dp[j + c] = max(dp[j + c], dp[j] + v);
        }
        else
        {
            for (int64_t j = N * C - c - 1; j >= 0; j--)
                if (dp[j] != INT64_MIN)
                    dp[j + c] = max(dp[j + c], dp[j] + v);
        }
    }

    int64_t max_value = 0;
    for (size_t i = 0; i < N * C; i++)
        max_value = max(max_value, dp[i]);

    cout << max_value << '\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