Submission #823889

#	Time	Username	Problem	Language	Result	Execution time	Memory
823889		12345678	Cloud Computing (CEOI18_clo)	C++17	100 / 100	614 ms	2136 KiB

clo

#include <bits/stdc++.h>

using namespace std;

const int nx=2e3+5, cx=51;
int n, m, c, f, p;
long long dp[2][nx*cx], ans=0;

struct com
{
    bool type;
    int c, f, v;
    com(bool type, int c, int f, int v): type(type), c(c), f(f), v(v){} 
    bool operator< (const com &o)
    {
        if (f==o.f) return type<o.type;
        return f<o.f;
    }
};
vector<com> v;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=0; i<n; i++) cin>>c>>f>>p, v.push_back(com(1, c, f, p));
    cin>>m;
    for (int i=0; i<m; i++) cin>>c>>f>>p, v.push_back(com(0, c, f, p));
    sort(v.begin(), v.end());
    for (int i=0; i<nx*cx; i++) dp[0][i]=dp[1][i]=-1e18;
    for (int i=n+m-1; i>=0; i--)
    {
        int cur=i%2, pv=1-cur;
        if (i==n+m-1) dp[pv][0]=0;
        com cr=v[i];
        for (int j=0; j<nx*cx; j++) dp[cur][j]=dp[pv][j];
        if (cr.type==1) for (int j=cr.c; j<nx*cx; j++) dp[cur][j]=max(dp[cur][j], dp[pv][j-cr.c]-cr.v);
        else for (int j=0; j+cr.c<nx*cx; j++) dp[cur][j]=max(dp[cur][j], dp[pv][j+cr.c]+cr.v);
    }
    for (int i=0; i<nx*cx; i++) ans=max(ans, dp[0][i]);
    cout<<ans;
}

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