제출 #1278430

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278430		k12_khoi	Cloud Computing (CEOI18_clo)	C++17	100 / 100	173 ms	1268 KiB

clo

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

#define ll long long
#define pii pair<int,int>
#define X first
#define Y second

const int N=2005;
const int MMM=1e5+5;
const ll oo=(long double)1e18+1;

struct Cloud
{
    int X,Y,Z;
} a[N],b[N];

bool cmpY(Cloud x,Cloud y)
{
    return x.Y<y.Y;
}

int n,request,sum,l; ll res;
ll dp[MMM];

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for (int i=1;i<=n;i++)
    cin >> a[i].X >> a[i].Y >> a[i].Z;

    cin >> request;
    for (int i=1;i<=request;i++)
    cin >> b[i].X >> b[i].Y >> b[i].Z;


    sort(a+1,a+n+1,cmpY);
    sort(b+1,b+request+1,cmpY);


    sum=1e5;
    for (int i=1;i<=sum;i++)
    dp[i]=-oo;

    sum=0;
    l=n;
    for (int i=request;i>=1;i--)
    {
        while (l>=1 and a[l].Y>=b[i].Y)
        {
            sum+=a[l].X;

            for (int j=sum;j>=a[l].X;j--)
            dp[j]=max(dp[j],dp[j-a[l].X]-a[l].Z);

            for (int j=a[l].X-1;j>=1;j--)
            dp[j]=max(dp[j],(ll)-a[l].Z);

            l--;
        }

        for (int j=0;j+b[i].X<=sum;j++)
        dp[j]=max(dp[j],dp[j+b[i].X]+b[i].Z);
    }

    res=0;
    for (int i=0;i<=sum;i++)
    res=max(res,dp[i]);

    cout << res;
}

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