Submission #957764

#	Time	Username	Problem	Language	Result	Execution time	Memory
957764		LucaIlie	Cloud Computing (CEOI18_clo)	C++17	100 / 100	323 ms	1384 KiB

clo

#include <bits/stdc++.h>

using namespace std;

struct task {
    int t, c, f, v;
};

const int MAX_N = 2000;
const int MAX_M = 2000;
const int MAX_C = 50;
const int MAX_CORES = MAX_M * MAX_C;
const long long INF = 1e15;
vector<task> events;
long long dp[MAX_CORES + 1];

int main() {
    int n, m;

    cin >> n;
    for ( int i = 0; i < n; i++ ) {
        int c, f, v;
        cin >> c >> f >> v;
        events.push_back( { 0, c, f, v } );
    }
    cin >> m;
    for ( int i = 0; i < m; i++ ) {
        int c, f, v;
        cin >> c >> f >> v;
        events.push_back( { 1, c, f, v } );
    }

    sort( events.begin(), events.end(), []( task a, task b ) {
        if ( a.f == b.f )
            return a.t < b.t;
        return a.f > b.f;
    } );

    dp[0] = 0;
    for ( int p = 1; p <= MAX_CORES; p++ )
        dp[p] = -INF;
    for ( auto e: events ) {
        if ( e.t == 0 ) {
            for ( int p = MAX_CORES; p - e.c >= 0; p-- )
                dp[p] = max( dp[p], dp[p - e.c] - e.v );
        } else {
            for ( int p = 0; p + e.c <= MAX_CORES; p++ )
                dp[p] = max( dp[p], dp[p + e.c] + e.v );
        }
    }

    long long ans = 0;
    for ( int p = 0; p <= MAX_CORES; p++ )
        ans = max( ans, dp[p] );

    cout << ans;

    return 0;
}

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