Submission #1161122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161122		AlgorithmWarrior	Cloud Computing (CEOI18_clo)	C++20	100 / 100	213 ms	1260 KiB

clo

#include <bits/stdc++.h>

using namespace std;

int const MAX=4005;
int const MAXC=1e5+5;
long long const INF=1e18;
struct event{
    int cap,crt,val,type;
    bool operator<(event ot){
        if(crt!=ot.crt)
            return crt>ot.crt;
        return type<ot.type;
    }
}events[MAX];
int n,m;
int total;

void read(){
    cin>>n;
    int i;
    for(i=1;i<=n;++i){
        cin>>events[i].cap>>events[i].crt>>events[i].val;
        events[i].type=1;
    }
    cin>>m;
    for(i=n+1;i<=n+m;++i){
        cin>>events[i].cap>>events[i].crt>>events[i].val;
        events[i].type=2;
    }
    total=n+m;
    sort(events+1,events+total+1);
}

long long dp[MAXC];

void maxself(long long& x,long long val){
    if(x<val)
        x=val;
}

void get_dp(){
    int i;
    for(i=1;i<MAXC;++i)
        dp[i]=-INF;
    int j;
    int sum=0;
    for(j=1;j<=total;++j){
        auto [cap,crt,val,type] = events[j];
        if(type==1){
            sum+=cap;
            for(i=sum;i>=cap;--i)
                maxself(dp[i],dp[i-cap]-val);
        }
        else{
            for(i=0;i<=sum-cap;++i)
                maxself(dp[i],dp[i+cap]+val);
        }
    }
}

long long get_answer(){
    long long answer=0;
    int i;
    for(i=0;i<MAXC;++i)
        maxself(answer,dp[i]);
    return answer;
}

int main()
{
    read();
    get_dp();
    cout<<get_answer();
    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