Submission #1313462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313462		hssaan_arif	Cloud Computing (CEOI18_clo)	C++20	36 / 100	632 ms	3916 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 = 2e5 + 5, M = 1e9 + 7, LG = 20;

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

bool comp(vector<int> a , vector<int> b){
    if (a[0] != b[0]){
        return a[0] > b[0];
    }
    return !a[3];
}

void solve(){
    cin >> n;

    vector<vector<int>> cp;

    for (int i=1 ; i<=n ; i++){
        cin >> u >> v >> w;
        cp.pb({v,u,w,0});
    }

    cin >> m;

    for (int i=1 ; i<=m ; i++){
        cin >> u >> v >> w;
        cp.pb({v,u,w,1});
    }

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

    for (auto i : cp){
        int c = i[1];
        int v = i[2];
        if (i[3]){
            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-1 ; 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: 0 / 18
• Subtask 3: 18 / 18
• Subtask 4: 0 / 18
• Subtask 5: 0 / 18
• Subtask 6: 0 / 10