Submission #481890

#	Time	Username	Problem	Language	Result	Execution time	Memory
481890		keertan	Cloud Computing (CEOI18_clo)	C++17	100 / 100	597 ms	2892 KiB

clo

/**
 * If you live in imaginary world when your imaginary situation encounter in 
 * real situation you can't enjoiy it because you have to do pending work.
 * {This pending work appeared because you wasted that time for your useless
 * imagianry thinking.}
 */
#include<bits/stdc++.h>
using namespace std;
#define int  int64_t
#define all(x) x.begin(),x.end()
#define all1(x) x.rbegin(),x.rend()
const int N=2e6+5;

int vis=0;
typedef struct A{
    int core;
    int rate;
    int price;
}node;
void solve(){
    int n;
    cin>>n;
    vector<node> z;
    node x;
    int mx=0;
    for (int i=0;i<n;i++){
        cin>>x.core>>x.rate>>x.price;
        x.price*=-1;
        z.push_back(x);
        mx+=x.core;
    }
    cin>>n;
    for (int i=0;i<n;i++){
        cin>>x.core>>x.rate>>x.price;
        x.core*=-1;
        z.push_back(x);
    }
    sort(all(z),[&](node a,node b){
        if (a.rate==b.rate){return a.price<b.price;}
        return a.rate>b.rate;
    });   
    n=z.size();
    vector<vector<int>> dp(2,vector<int>(mx+1,INT64_MIN));
    dp[0][0]=dp[1][0]=0;
    for (int i=0;i<n;i++){
        int cur=i&1,prv=~i&1;
        for (int j=0;j<=mx;j++){
            int con=j-z[i].core;
            dp[cur][j]=dp[prv][j];
            if (0<=con && con<=mx && dp[prv][con]!=INT64_MIN){
            dp[cur][j]=max(dp[prv][j],z[i].price+dp[prv][con]);}
        }
    }
    int ans=0;
    for (int i=0;i<=mx;i++){ans=max(ans,dp[(n-1)&1][i]);}
    cout<<ans;
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tq=1;
    //cin>>tq;
    for (;tq;tq--){solve();}
}
//is a bruteforce possible?
//think greedier, make more assumptions
// if we you find solution using loop to decrease complexity use bs
//stuck for more than 5 minutes? move on 

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