Submission #443295

#	Time	Username	Problem	Language	Result	Execution time	Memory
443295		LittleCube	Cloud Computing (CEOI18_clo)	C++14	18 / 100	512 ms	1080 KiB

clo

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

struct P
{
    ll c, f, v;
    P(ll c, ll f, ll v) : c(c), f(f), v(v){};
    P() : c(0), f(0), v(0){};
};

ll M, N, dp[100001], cost, mxsize;
P computer[2005], order[2005];

void debug()
{
    if (0)
        for (int i = 1; i <= mxsize; i++)
            cout << dp[i] << " \n"[i == mxsize];
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> computer[i].c >> computer[i].f >> computer[i].v;
    sort(computer + 1, computer + 1 + N, [](P p1, P p2)
         {
             if (p1.f != p2.f)
                 return p1.f < p2.f;
             return p1.c * p2.v > p2.c * p1.v;
         });

    cin >> M;
    for (int i = 1; i <= M; i++)
        cin >> order[i].c >> order[i].f >> order[i].v;

    sort(order + 1, order + 1 + M, [](P p1, P p2)
         { return p1.f < p2.f; });

    for (int i = 1; i <= N; i++)
    {
        computer[i].c += computer[i - 1].c;
        cost += computer[i].v;
    }
    mxsize = computer[N].c;

    for (int j = 1; j <= N; j++)
        dp[computer[j].c] = max(dp[computer[j].c], dp[computer[j - 1].c] + computer[j].v);

    for (int i = 1; i <= M; i++)
    {
        ll idx = prev(lower_bound(computer, computer + 1 + N,
                                  P(0, order[i].f, 0), [](P p1, P p2)
                                  { return p1.f < p2.f; }))
                     ->c;
        ll idx2 = lower_bound(computer, computer + 1 + N,
                              P(0, order[i].f, 0), [](P p1, P p2)
                              { return p1.f < p2.f; }) -
                  computer;
        for (int j = mxsize; j >= idx + order[i].c; j--)
            dp[j] = max({dp[j], dp[j - order[i].c] + order[i].v});

        debug();

        for (int j = 1; j <= mxsize; j++)
            dp[j] = max(dp[j], dp[j - 1]);

        debug();

        for (int j = idx2; j <= N; j++)
            dp[computer[j].c] = max(dp[computer[j].c], dp[computer[j - 1].c] + computer[j].v);

        debug();

        for (int j = 1; j <= mxsize; j++)
            dp[j] = max(dp[j], dp[j - 1]);

        debug();
    }
    cout << dp[mxsize] - cost << '\n';
}

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