Submission #443313

#TimeUsernameProblemLanguageResultExecution timeMemory
443313Haruto810198Cloud Computing (CEOI18_clo)C++17
18 / 100
4 ms3788 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[MAX][MAX];

int res;

bool cmp_by_rate(vi a, vi b){
    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};
    }
    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);

    dp[0][0] = (cpu[0][1] >= work[0][1]) ? max((int)0, work[0][2] - cpu[0][2]) : 0;

    FOR(i, 1, n-1, 1){
        dp[i][0] = max( dp[i-1][0], ((cpu[i][1] >= work[0][1]) ? max((int)0, work[0][2] - cpu[i][2]) : 0) );
    }

    FOR(j, 1, m-1, 1){
        dp[0][j] = max( dp[0][j-1], ((cpu[0][1] >= work[j][1]) ? max((int)0, work[j][2] - cpu[0][2]) : 0) );
    }

    FOR(i, 1, n-1, 1){
        FOR(j, 1, m-1, 1){
            dp[i][j] = max({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
            if(cpu[i][1] >= work[j][1]){
                dp[i][j] = max(dp[i][j], dp[i-1][j-1] + work[j][2] - cpu[i][2]);
            }
        }
    }

    cout<<dp[n-1][m-1]<<'\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...