제출 #1190155

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190155		DangKhoizzzz	Cloud Computing (CEOI18_clo)	C++20	100 / 100	234 ms	1336 KiB

clo

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18;
const int maxn = 2e3 + 7;

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

bool comp0(info a , info b) {return (a.f < b.f);}


int n , m , dp[maxn*51];
info a[maxn] , b[maxn];

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i].c >> a[i].f >> a[i].v;
    }
    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> b[i].c >> b[i].f >> b[i].v;
    }
    sort(a+1 , a+n+1 , comp0);
    sort(b+1 , b+m+1 , comp0);

    for(int x = 1; x < maxn*51; x++) dp[x] = -INF;

    int j = m;

    for(int i = n; i >= 1; i--)
    {
        for(int x = maxn*50; x >= a[i].c; x--)
        {
            dp[x] = max(dp[x] , dp[x - a[i].c] - a[i].v);
        }

        while(j > 0 && b[j].f > a[i].f) j--;

        while(j > 0 && b[j].f > a[i-1].f)
        {
            for(int x = 0; x < maxn*50; x++)
            {
                dp[x] = max(dp[x + b[j].c] + b[j].v , dp[x]);
            }
            j--;
        }
    }

    cout << *max_element(dp+0 , dp+maxn*51) << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    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