제출 #943403

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
943403		htphong0909	Cloud Computing (CEOI18_clo)	C++17	100 / 100	502 ms	2392 KiB

clo

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

const int MAX = 2000 * 50;
int DP[2][MAX + 10];

int32_t main()
{
    vector<array<int, 3>> items;
    int k1;
    cin >> k1;
    for (int i = 0; i < k1; i++)
    {
        int c, f, v;
        cin >> c >> f >> v;
        items.push_back({f, c, -v});
    }
    
    int k2;
    cin >> k2;
    for (int i = 0; i < k2; i++)
    {
        int c, f, v;
        cin >> c >> f >> v;
        items.push_back({f, -c, v});
    }
    
    sort(items.rbegin(), items.rend());
    memset(DP, -0x3f, sizeof DP);
    
    int ans = 0;
    DP[0][0] = 0;
    bool s = 0;
    for (auto [f, c, v] : items)
    {
        s = !s;
        for (int i = 0; i <= MAX; i++)
        {
            DP[s][i] = DP[!s][i];
            if (i - c <= MAX && i - c >= 0) DP[s][i] = max(DP[s][i], DP[!s][i - c] + v);
            ans = max(ans, DP[s][i]);
        }
    }
    
    cout << ans;
    return 0;
}

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