Submission #1313475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313475		hssaan_arif	Cloud Computing (CEOI18_clo)	C++20	100 / 100	330 ms	2252 KiB

clo

#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;

#define endl "\n"
#define pb push_back
#define int long long
#define fi first
#define se second

const int N = 1e5, M = 1e9 + 7, LG = 20;

struct pc{
    int f = 0 , v = 0 , c = 0;
    bool tp = 0; 
};

int n , A[N] , u , v , w , m;
int dp[2*N];

bool comp(pc a , pc b){
    if (a.f != b.f){
        return a.f > b.f;
    }
    return !a.tp;
}

void solve(){
    cin >> n;

    vector<pc> cp;
    pc k;

    for (int i=1 ; i<=n ; i++){
        cin >> k.c >> k.f >> k.v;
        k.tp = 0;
        cp.pb(k);
    }

    cin >> m;

    for (int i=1 ; i<=m ; i++){
        cin >> k.c >> k.f >> k.v;
        k.tp = 1;
        cp.pb(k);
    }

    
    fill(dp, dp + N + N, -1e18);
    dp[0] = 0;
    sort(cp.begin(),cp.end(),comp);

    for (auto i : cp){
        int c = i.c;
        int v = i.v;
        if (i.tp){
            for (int i=0 ; i+c<=N ; i++){
                if (dp[i+c] == -1e18) continue;
                dp[i] = max(dp[i] , dp[i+c] + v);
            }
        }else{
            for (int i=N ; i>=c ; i--){
                if (dp[i-c] == -1e18) continue;
                dp[i] = max(dp[i] , dp[i-c] - v);
            }
        }
    }
    
    int ans = 0;

    for (int i=0 ; i<=N ; i++){
        ans = max(ans , dp[i]);
    }

    cout << ans << endl;
}

signed main(){
    // freopen("" , "r" , stdin);
    // freopen("" , "w" , stdout);
    // cout << setprecision(30);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ts = 1;
    // cin >> ts;
    while(ts--){
        solve();
    }
}

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