제출 #1325733

#제출 시각아이디문제언어결과실행 시간메모리
1325733DanielPr8Cloud Computing (CEOI18_clo)C++20
100 / 100
321 ms1336 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()

int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    ll n, m;
    cin >> n;
    vector<tuple<ll,ll,ll>> ord;// freq, amount, price
    for(ll i = 0; i < n; ++i){
        ll a, b, c;
        cin >> a >> b >> c;
        ord.pb({b, a, -c});
    }
    cin >> m;
    for(ll i = 0; i < m; ++i){
        ll a, b, c;
        cin >> a >> b >> c;
        ord.pb({b, -a, c});
    }
    sort(all(ord),greater<tuple<ll,ll,ll>>());
    vll dp(max(n,m)*50+1, -1e14);
    dp[0]=0;
    for(ll i = 1; i <= n+m; ++i){
        auto [f, am, pr] = ord[i-1];
        if(am<0){
            for(ll j = 0; j < dp.size(); ++j){
                if(j>=am && j-am<dp.size())dp[j] = max(dp[j], dp[j-am]+pr);
            }
        }
        else{
            for(ll j = dp.size()-1; j >=0; --j){
                if(j>=am && j-am<dp.size())dp[j] = max(dp[j], dp[j-am]+pr);
            }
        }

    }
    cout << *max_element(all(dp));
}
#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...