Submission #1273481

#TimeUsernameProblemLanguageResultExecution timeMemory
1273481nexelleCloud Computing (CEOI18_clo)C++20
0 / 100
11 ms4968 KiB
#include<bits/stdc++.h>
using namespace std;

#define nl "\n"
#define int long long
#define ll long long
#define str string

#define Pb push_back
#define pB pop_back
#define all(a) (a).begin(),(a).end()

const ll inf = 1e15+1;

const ll N = 2*2e3 + 5;
const ll M = 2e5;

#define pii pair<int,int>
#define piii pair<int,pair<int,int>>

int dx[] = {-1, -1,  0, 1, 0, 1};
int dy[] = { 0, -1, -1, 0, 1, 1};

vector<vector<ll>> DP(2, vector<ll>(M+5, -inf));

void solve() {
    int n; cin >> n;
    
    vector<vector<ll>> total;
    for(int i=1;i<=n;i++) {
        ll c,f,v; cin >> c >> f >> v;
        total.Pb({-f,-c,v,1});
    }
    
    int m; cin >> m;
    for(int i=1;i<=m;i++) {
        ll c,f,v; cin >> c >> f >> v;
        total.Pb({-f,c,v,2});
    }

    sort(all(total));

    //DP[i][j] = profit maks, apabila tersisa j inti pada indeks i
    DP[0][0] = 0;
    for(int i=1;i<=n+m;i++) {
        int clock = total[i][0];
        int inti = abs(total[i][1]);
        int harga = total[i][2];
        int tipe = total[i][3];
        
        // auto [inti, clock, harga, tipe] = total[i-1];
        // cout << inti << " " << clock << " " << harga << " " << tipe << nl;

        for(int j=0;j<=M;j++) DP[i%2][j] = DP[(i+1)%2][j];
        
        //Kalo komputer ini dibeli
        if(tipe == 1) {
            for(int j=1;j<=M;j++) 
                if(inti <= j) 
                    DP[i%2][j] = max(DP[i%2][j], DP[(i+1)%2][j-inti] - harga);
        } 
        // Kalo keinginan pelanggan diturutin
        if(tipe == 2) {
            for(int j=1;j<=M;j++) 
                if(j+inti <= M) DP[i%2][j] = max(DP[i%2][j], DP[(i+1)%2][j+inti] + harga);
        }
    }

    ll ans = 0;
    for(int j=0;j<=M;j++) ans = max(ans, DP[(n+m)%2][j]);
    cout << ans << nl;
}

signed main() {
    int T=1; //cin >> T;
    for(int x=1;x<=T;x++) 
        solve();
}  
#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...