제출 #971860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971860		0x34c	Cloud Computing (CEOI18_clo)	C++17	0 / 100	1 ms	604 KiB

clo

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#define int ll

using namespace std;

struct node
{
    int c, f, v;
};

const int MAX_C = 201;
const int INF = 1e9;

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

    int N, M;
    cin >> N;

    vector<node> pc(N);
    for (int i = 0; i < N; i++)
    {
        int c, f, v;
        cin >> c >> f >> v;

        pc[i] = {c, f, v};
    }

    cin >> M;
    vector<node> qr(M);
    for (int i = 0; i < M; i++)
    {
        int c, f, v;
        cin >> c >> f >> v;

        qr[i] = {c, f, v};
    }

    sort(pc.begin(), pc.end(), [&](node &a, node &b)
         {  if(a.f == b.f) return a.c > b.c; return a.f > b.f; });
    sort(qr.begin(), qr.end(), [&](node &a, node &b)
         { if(a.f == b.f) return a.c > b.c; return a.f > b.f; });

    for (node &n : pc)
    {
        cout << n.c << ' ' << n.f << ' ' << n.v << endl;
    }

    for (node &n : qr)
    {
        cout << n.c << ' ' << n.f << ' ' << n.v << endl;
    }

    int dp[M + 1][N + 1][MAX_C];
    fill_n(&dp[0][0][0], (M + 1) * (N + 1) * MAX_C, -INF);
    dp[0][0][0] = 0;
    int mx = 0;
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
        {
            for (int c = MAX_C - 1; c >= 0; c--)
            {
                if (dp[i][j][c] == -INF)
                    continue;

                // skip zakazku
                dp[i + 1][j][c] = max(dp[i + 1][j][c], dp[i][j][c]);
                mx = max(mx, dp[i + 1][j][c]);

                // skip pc
                dp[i][j + 1][c] = max(dp[i][j + 1][c], dp[i][j][c]);
                mx = max(mx, dp[i][j + 1][c]);

                if (qr[i].f <= pc[j].f)
                {
                    dp[i][j + 1][c + pc[j].c] = max(dp[i][j + 1][c + pc[j].c], dp[i][j][c] - pc[j].v);
                    mx = max(mx, dp[i][j + 1][c + pc[j].c]);
                }

                // take next
                if (qr[i].f <= pc[j].f && qr[i].c <= c + pc[j].c)
                {
                    dp[i + 1][j + 1][c + pc[j].c - qr[i].c] = max(dp[i + 1][j + 1][c + pc[j].c - qr[i].c], dp[i][j][c] + (qr[i].v - pc[j].v));
                    mx = max(mx, dp[i + 1][j + 1][c + pc[j].c - qr[i].c]);
                }

                // take using c
                if (qr[i].c <= c)
                {
                    dp[i + 1][j][c - qr[i].c] = max(dp[i + 1][j][c - qr[i].c], dp[i][j][c] + qr[i].v);
                    mx = max(mx, dp[i + 1][j][c - qr[i].c]);
                }
            }
        }

    cout << mx << endl;
}

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