Submission #1299618

#TimeUsernameProblemLanguageResultExecution timeMemory
1299618notbrainingCloud Computing (CEOI18_clo)C++20
100 / 100
1008 ms2172 KiB
//#pragma GCC optimize ("O3")
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#include <cassert>
#include<algorithm>
#include <cstring>
#include<unordered_set>
#include<queue>
#include <array>
#include<cmath>
#include<unordered_map>
#include<queue>
#include <list>
#include <bitset>
using namespace std;
#define int long long
#define pii pair<int,int>
#define LL long long
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt”)
int INF = 1e18;
const int MAXSIZE = 1e5 + 1;
const int zero = 1e5;
int dp[MAXSIZE];
int ndp[MAXSIZE];
int32_t main(){
    cin.tie(0)->sync_with_stdio(0);

    int n, m;
    cin >> n;
    vector<pair<pii, int>>comps(n);
    // F, 0=request, 1 = computer, Cores, Valuecost
    vector<pair<pii, pii>>events;
    for(int i = 0; i < n; ++i){
        int C, F, V;
        cin >> C >> F >> V;
        events.push_back({{F, 1}, {C, V}});
    }
    cin >> m;
    for(int i = 0; i < m; ++i){
        int C, F, V;
        cin >> C >> F >> V;
        events.push_back({{F, 0}, {C, V}});
    }
    //sort in decredasing order btw
    sort(events.begin(), events.end(), greater<pair<pii, pii>>());
    int x = events.size();
    memset(dp, -0x3f, sizeof(dp));
    dp[0] = 0;
    for(int i = 0; i < x; ++i){
        memset(ndp, -0x3f, sizeof(ndp));
        for(int j = 0; j <= 1e5; ++j){
            int prof = dp[j];
            int v = events[i].second.second;
            if(events[i].first.second == 0){
                //this means you are selling
                if(j >= events[i].second.first){
                    ndp[j - events[i].second.first] = max(ndp[j - events[i].second.first], v + prof);
                }
            } else{
                //this means you are buying
                if(j + events[i].second.first <= 1e5)
                    ndp[j + events[i].second.first] = max(ndp[j + events[i].second.first], dp[j] - v);
            }
            ndp[j] = max(ndp[j], dp[j]);

        }
        swap(dp, ndp);
    }
    int ans = 0;
    for(int i = 0; i <= 1e5; ++i){
        ans = max(ans, dp[i]);
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...