제출 #443303

#제출 시각아이디문제언어결과실행 시간메모리
443303Haruto810198Cloud Computing (CEOI18_clo)C++17
18 / 100
455 ms2204 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}

int dp_inc[50 * MAX + 1]; /// dp[cores] = max. income
int dp_exp[50 * MAX + 1]; /// dp[cores] = min. expense

int res;

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

    cin>>m;
    FOR(i, 0, m-1, 1){
        int c, r, p;
        cin>>c>>r>>p;
        work[i] = {c, r, p};
    }

    dp_exp[0] = 0;
    FOR(i, 1, 50*MAX, 1){
        dp_exp[i] = LNF;
    }

    FOR(i, 0, n-1, 1){
        int cores = cpu[i][0], price = cpu[i][2];
        for(int j=50*MAX; j>=0; j--){
            if(j >= cores){
                dp_exp[j] = min(dp_exp[j], dp_exp[j - cores] + price);
            }
        }
    }

    dp_inc[0] = 0;
    FOR(i, 1, 50*MAX, 1){
        dp_inc[i] = -LNF;
    }

    FOR(i, 0, m-1, 1){
        int cores = work[i][0], price = work[i][2];
        for(int j=50*MAX; j>=0; j--){
            if(j >= cores){
                dp_inc[j] = max(dp_inc[j], dp_inc[j - cores] + price);
            }
        }
    }

    res = 0;
    int Max_inc = 0;
    FOR(i, 0, 50*MAX, 1){
        Max_inc = max(Max_inc, dp_inc[i]);
        res = max(res, Max_inc - dp_exp[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...