제출 #443297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
443297		Haruto810198	Cloud Computing (CEOI18_clo)	C++17	0 / 100	3095 ms	620 KiB

clo

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

vi cores;
int dp[50 * MAX + 1]; /// dp[n. of cores] = max. income
int res;

bool cmp_by_rate(vi a, vi b){
    return (a[1] > b[1]);
}

int solve(int mask){

    int inc = 0, exp = 0;

    /// cores
    cores.clear();

    FOR(i, 0, n-1, 1){
        if((mask & (1<<i)) != 0){
            exp += cpu[i][2];
            FOR(j, 1, cpu[i][0], 1){
                cores.pb(cpu[i][1]);
            }
        }
    }

    FOR(i, 1, 50, 1){
        cores.pb(0);
    }
    cores.pb(INF);

    sort(cores.begin(), cores.end());
    reverse(cores.begin(), cores.end());

    int C = szof(cores) - 1;

    /// dp
    FOR(i, 0, C, 1){
        dp[i] = 0;
    }

    FOR(i, 0, m-1, 1){ /// i = id. of work

        int core = work[i][0], rate = work[i][1], profit = work[i][2];

        for(int j=C; j>=1; j--){ /// j = id. of dp[]
            if(j >= core and cores[j] >= rate){
                dp[j] = max(dp[j], dp[j - core] + profit);
            }
        }

    }

    FOR(i, 0, C, 1){
        inc = max(inc, dp[i]);
    }

    //cerr<<"solve("<<mask<<") = "<<inc - exp<<endl;

    return (inc - exp);

}

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};
    }
    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};
    }
    sort(work, work+m, cmp_by_rate);

    /// enum. subset of computers
    res = 0;
    FOR(i, 0, (1<<n)-1, 1){
        res = max(res, solve(i));
    }

    cout<<res<<'\n';

    return 0;

}

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