제출 #1273478

#제출 시각아이디문제언어결과실행 시간메모리
1273478kausarmeCloud Computing (CEOI18_clo)C++20
100 / 100
474 ms2112 KiB
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;typedef long double ld;typedef pair<int,int> pii;
const ll mod = 1e9+7, N = 2e6+7, M = 2e6+7, INF = INT_MAX/10;
ll powe(ll x, ll y){ x = x%mod, y=y%(mod-1);ll ans = 1;while(y>0){if (y&1){ans = (1ll * x * ans)%mod;}y>>=1;x = (1ll * x * x)%mod;}return ans;}

void solve(){
    const ll NEG = -1e18;
    vector<pair<ll, pair<ll,ll>>> ev;
    
    ll n; 
    cin >> n;
    ll sumC = 0;
    for(int i = 0; i < n; i++){
        ll c, f, v; 
        cin >> c >> f >> v;
        ev.push_back({f, {c, -v}}); 
        sumC += c;
    }
    
    ll m; 
    cin >> m;
    for(int i = 0; i < m; i++){
        ll C, F, V; 
        cin >> C >> F >> V;
        ev.push_back({F, {-C, V}});  
        sumC += C;
    }

    sort(ev.begin(), ev.end());

    vector<ll> dp(sumC+1, NEG);
    dp[0] = 0;

    for(int idx = (int)ev.size() - 1; idx >= 0; idx--){
        ll k = ev[idx].second.first;   // cores
        ll p = ev[idx].second.second;  // profit
        if(k > 0){
            for(int used = sumC - k; used >= 0; used--){
                dp[used + k] = max(dp[used + k], dp[used] + p);
            }
        } else {
            for(int used = -k; used <= sumC; used++){
                dp[used + k] = max(dp[used + k], dp[used] + p);
            }
        }
    }

    ll ans = 0;
    for(int i = 0; i <= sumC; i++) ans = max(ans, dp[i]);
    cout << ans << "\n";
}
signed main(){
    fast;
    solve();
    return 0;
}
#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...