Submission #1304101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304101		Warinchai	Cloud Computing (CEOI18_clo)	C++20	100 / 100	395 ms	1488 KiB

clo

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

int dp[100005];
int inf=1e15;
vector<pair<int,int>>have[2005];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    vector<int>val;
    vector<pair<int,pair<int,int>>>temp;
    vector<pair<int,pair<int,int>>>buy;
    for(int i=1;i<=n;i++){
        int c,f,v;cin>>c>>f>>v;
        val.push_back(f);
        temp.push_back({f,{-v,c}});
    }
    sort(val.begin(),val.end());
    val.erase(unique(val.begin(),val.end()),val.end());
    for(auto x:temp){
        int f=x.first;
        auto v=x.second;
        int id=lower_bound(val.begin(),val.end(),f)-val.begin();
        have[id].push_back(v);
    }
    int m;cin>>m;
    for(int i=1;i<=m;i++){
        int c,f,v;cin>>c>>f>>v;
        buy.push_back({f,{v,-c}});
    }
    sort(buy.begin(),buy.end());
    reverse(buy.begin(),buy.end());
    int cur=0;
    for(int i=1;i<=1e5;i++)dp[i]=-inf;
    for(int i=val.size()-1;i>=0;i--){
        int f=val[i];
        for(;cur<m&&buy[cur].first>f;cur++){
            //cerr<<buy[cur].first<<"\n";
            int cost=buy[cur].second.first;
            int num=buy[cur].second.second;
            //cerr<<"item:"<<cost<<" "<<num<<"\n";
            for(int i=0;i<=1e5;i++){
                if(i-num>1e5)break;
                dp[i]=max(dp[i],dp[i-num]+cost);
            }
        }
        for(auto [cost,num]:have[i]){
            //cerr<<"item:"<<cost<<" "<<num<<"\n";
            for(int i=1e5;i>=0;i--){
                if(i-num<0)break;
                dp[i]=max(dp[i],dp[i-num]+cost);
            }
        }
        //cerr<<"f:"<<f<<"\n";
    }
    for(;cur<m;cur++){
        //cerr<<buy[cur].first<<"\n";
        int cost=buy[cur].second.first;
        int num=buy[cur].second.second;
        //cerr<<"item:"<<cost<<" "<<num<<"\n";
        for(int i=0;i<=1e5;i++){
            if(i-num>1e5)break;
            dp[i]=max(dp[i],dp[i-num]+cost);
        }
    }
    int ans=0;
    for(int i=0;i<=1e5;i++)ans=max(ans,dp[i]);
    cout<<ans<<"\n";
}

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