Submission #1188750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188750		vukhacminh	Cloud Computing (CEOI18_clo)	C++20	100 / 100	579 ms	2032 KiB

clo

/**
*    Author :  Vu Khac Minh
*
**/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9+7;
struct store
{
    int c,f,v;
}a[maxn*5];
int n,m,all;
long long  dp[2][maxn];
bool cmp(store &x,store &y)
{
    if(x.f == y.f) return x.v<y.v;
    return x.f > y.f;
}
int main()
{
    cin>>n;
    for(int i =1;i<=n;i++)
    {
        cin>>a[i].c>>a[i].f>>a[i].v;
        all+=a[i].c;
        a[i].v = -a[i].v;
    }
    cin>>m;
    for(int i =n+1;i<=n+m;i++)
    {
        cin>>a[i].c>>a[i].f>>a[i].v;
        a[i].c = -a[i].c;
    }
    sort(a+1,a+m+n+1,cmp);
    for(int i =0;i<=all;i++) dp[0][i] = dp[1][i] = -1e14;
    dp[0][0] = 0;
    for(int i =1;i<=n+m;i++)
    {
        for(int j = 0;j<=all;j++) dp[i&1][j] = -1e14;
        for(int j = 0;j<=all;j++)
        {
            dp[i&1][j] = max(dp[(i-1)&1][j],dp[i&1][j]);
                int state = j - a[i].c;
                if(state>=0 && state<=all && dp[(i-1)&1][state] > -1e14/2)
                    dp[i&1][j] = max(dp[i&1][j],dp[(i-1)&1][state] + a[i].v);
        }
    }
    long long  res = 0;
    for(int  i = 0;i<=all;i++) res = max(res,dp[(n+m)&1][i]);
    cout<<res;
    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