제출 #448340

#제출 시각아이디문제언어결과실행 시간메모리
448340mnair797Cloud Computing (CEOI18_clo)C++14
100 / 100
629 ms2400 KiB
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define double long double
 
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
 
#define vi vector<int>
#define pii pair<int, int>
 
#define F first
#define S second
 
#define pb push_back
#define eb emplace_back
#define mkp make_pair
 
const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;
 
const int MAX = 2010;
 
int n, m;
vi cpu[MAX]; /// computers: {cores, rate, price}
vi work[MAX]; /// works: {cores, rate, price}
 
vector<vi> items;
 
int dp[50 * MAX + 1];
int tmp[50 * MAX + 1];
 
bool cmp_by_rate(vi a, vi b){
    if(a[1] == b[1]) return (a[0] > b[0]);
    return (a[1] > b[1]);
}
 
signed main(){
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin>>n;
    FOR(i, 0, n-1, 1){
        int c, r, p;
        cin>>c>>r>>p;
        cpu[i] = {c, r, p};
        items.pb({c, r, -p});
    }
    //sort(cpu, cpu+n, cmp_by_rate);
 
    cin>>m;
    FOR(i, 0, m-1, 1){
        int c, r, p;
        cin>>c>>r>>p;
        work[i] = {c, r, p};
        items.pb({-c, r, p});
    }
    //sort(work, work+m, cmp_by_rate);
 
    sort(items.begin(), items.end(), cmp_by_rate);
 
    dp[0] = 0;
    FOR(i, 1, 50*MAX, 1){
        dp[i] = -LNF;
    }
 
    for(auto I : items){
 
        int w = I[0], v = I[2];
 
        FOR(i, 0, 50*MAX, 1){
            if(0 <= i-w and i-w <= 50*MAX){
                tmp[i] = max(dp[i], dp[i - w] + v);
            }
            else{
                tmp[i] = dp[i];
            }
        }
 
        FOR(i, 0, 50*MAX, 1){
            dp[i] = tmp[i];
        }
 
    }
 
    int res = -LNF;
    FOR(i, 0, 50*MAX, 1){
        res = max(res, dp[i]);
    }
 
    cout<<res<<'\n';
 
    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...