oj.uz

Submission #972023

# Submission time Handle Problem Language Result Execution time Memory
972023 2024-04-29T18:03:15 Z 0x34c Cloud Computing (CEOI18_clo) C++17
36 / 100
 3000 ms 6748 KB 
#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; });

    int dp[2][N + 1][MAX_C];
    for (int i = 0; i < 2; i++)
        for (int j = 0; j <= N; j++)
            for (int c = 0; c < MAX_C; c++)
                dp[i][j][c] = -INF;

    int cur = 0, nxt = 1;
    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[cur][j][c] == -INF)
                    continue;

                // skip zakazku
                if (i + 1 <= M)
                {
                    dp[nxt][j][c] = max(dp[nxt][j][c], dp[cur][j][c]);
                    mx = max(mx, dp[nxt][j][c]);
                }

                if (j + 1 <= N)
                {
                    // skip pc
                    dp[cur][j + 1][c] = max(dp[cur][j + 1][c], dp[cur][j][c]);
                    mx = max(mx, dp[cur][j + 1][c]);
                }

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

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

                // take using c
                if (i < M && qr[i].c <= c)
                {
                    dp[nxt][j][c - qr[i].c] = max(dp[nxt][j][c - qr[i].c], dp[cur][j][c] + qr[i].v);
                    mx = max(mx, dp[nxt][j][c - qr[i].c]);
                }
            }
        }
        swap(cur, nxt);
        for (int j = 0; j <= N; j++)
            for (int c = 0; c < MAX_C; c++)
                dp[nxt][j][c] = -INF;
    }
    cout << mx << endl;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 21 ms 348 KB Output is correct
6 Correct 12 ms 348 KB Output is correct
7 Correct 19 ms 596 KB Output is correct
8 Correct 13 ms 348 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 19 ms 3164 KB Output is correct
6 Correct 16 ms 3164 KB Output is correct
7 Correct 33 ms 6744 KB Output is correct
8 Incorrect 14 ms 6744 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 16 ms 1116 KB Output is correct
6 Correct 34 ms 1164 KB Output is correct
7 Correct 28 ms 1116 KB Output is correct
8 Correct 18 ms 1116 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 16 ms 5208 KB Output is correct
4 Correct 25 ms 544 KB Output is correct
5 Execution timed out 3074 ms 6748 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 163 ms 2244 KB Output is correct
4 Correct 1270 ms 2996 KB Output is correct
5 Execution timed out 3011 ms 6744 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 21 ms 348 KB Output is correct
6 Correct 12 ms 348 KB Output is correct
7 Correct 19 ms 596 KB Output is correct
8 Correct 13 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 19 ms 3164 KB Output is correct
14 Correct 16 ms 3164 KB Output is correct
15 Correct 33 ms 6744 KB Output is correct
16 Incorrect 14 ms 6744 KB Output isn't correct
17 Halted 0 ms 0 KB -