Submission #1273474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273474		nexelle	Cloud Computing (CEOI18_clo)	C++20	18 / 100	951 ms	4940 KiB

clo

#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};

struct Mint{ll c, f, v, t;};
bool operator<(const Mint &a, const Mint &b) {
    //Prioritaskan yang punya clock terbesar
    if(a.f == b.f) {
        if(a.t == b.t) {
            //Prioritaskan komputer dengan inti lebih tinggi untuk komputer yang ingin dibeli
            //Dan prioritaskan komputer dengan inti lebih rendah yang diinginkan pelanggan
            if(a.t == 1) {
                //Prioritaskan harga lebih rendah
                if(a.c == b.c) return a.v < b.v;
                return a.c > b.c;
            }
            if(a.c == b.c) return a.v < b.v;
            return a.c < b.c;
        } 
        //Prioritaskan komputer yang ingin dibeli daripada komputer yang diinginkan pelanggan
        return a.t<b.t;
    }
    return a.f>b.f;
}

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

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

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