제출 #1064477

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

clo

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

const int maxn = 2003;
const int N = 1e7 + 3;
const ll inf = 1e18;
int n, m;
struct Edge{
    int c;
    ll f, v;
};

Edge st[2 * maxn + 7];

bool cmp(Edge a, Edge b)
{
    if(a.f == b.f) return a.c > b.c;
    return a.f > b.f;
}

int main()
{
    //freopen("CLOUDCOMPUTING.INP", "r", stdin);
    //freopen("CLOUDCOMPUTING.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int c;
        ll f, v;
        cin >> c >> f >> v;
        st[i].c = c;
        st[i].f = f;
        st[i].v = -v;
    }
    cin >> m;
    for(int i = 1 + n; i <= n + m; i++)
    {
        int c;
        ll f, v;
        cin >> c >> f >> v;
        st[i].c = -c;
        st[i].f = f;
        st[i].v = v;
    }
    sort(st + 1, st + n + m + 1, cmp);
    vector<ll>L(N + 3, -inf);
    vector<ll>P(N + 3, -inf);
    ll tmp = -inf;
    ll res = 0;
    for(int i = 1; i <= n + m; i++)
    {
        res += st[i].c;
        tmp = max(tmp, res);
    }
    P[0] = 0;
    ll ans = -inf;

    for(int i = 1; i <= n + m; i++)
    {
        for(int j = tmp + 3; j >= 0; j--)
        {
            L[j] = P[j];
            if(j >= st[i].c)
            {
                L[j] = max(L[j], P[j - st[i].c] + st[i].v);
               // dp[i][j] = max(dp[i][j], dp[i - 1][j - st[i].c] + st[i].v);
                ans = max(ans, L[j]);
               // cout << i << ' ' << j << ' ' << L[j] << '\n';
            }
        }
        P = L;
    }
    cout << ans;
}

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