Submission #1136384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136384		nrg_studio	Cloud Computing (CEOI18_clo)	C++20	36 / 100	304 ms	1096 KiB

clo

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define v vector

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n, c, f, val; cin >> n;
    v<pair<int,pii>> pool;
    F0R(i,n) {
        cin >> c >> f >> val;
        pool.pb({f,{val,c}});
    }
    int m; cin >> m;
    F0R(i,m) {
        cin >> c >> f >> val;
        pool.pb({f,{-val,-c}});
    }
    sort(all(pool));

    ll ans = 0;
    v<ll> dp(2000*50+1,INT_MIN);
    dp[0] = 0;

    while (pool.size()) {
        pii x = pool.back().s; pool.pop_back();
        
        if (x.s>0) {
            for (int i=2000*50;i>=0;i--) {
                if (dp[i]!=INT_MIN && i+x.s>=0) {
                    chmax(dp[i+x.s],dp[i]-x.f);
                }
            }
        } else {
            F0R(i,2000*50+1) {
                if (dp[i]!=INT_MIN && i+x.s>=0) {
                    chmax(dp[i+x.s],dp[i]-x.f);
                }
            }
        }
        
    }
    for (ll i : dp) {chmax(ans,i);}
    cout << ans << '\n';

    // constant factor is low maybe? can't think of any other solution
    
    /*int m = 50;
    v<int> a;
    FOR(i,1,51) {
        F0R(j,m/50) {a.pb(i);}
    }

    unordered_set<int> dp = {0};
    int m2 = 0;
    for (int i : a) {
        unordered_set<int> nxt = {0};
        for (int j : dp) {
            nxt.insert(j+i);
            nxt.insert(j);
        } dp = nxt;
        m2 = max(m2,(int)dp.size());
    } 
    cout << m2 << '\n';*/
}

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