Submission #500734

#	Time	Username	Problem	Language	Result	Execution time	Memory
500734		sberens	Cloud Computing (CEOI18_clo)	C++17	100 / 100	929 ms	1996 KiB

clo

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template<typename K> using hset = gp_hash_table<K, null_type>;
template<typename K, typename V> using hmap = gp_hash_table<K, V>;


using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define smax(x, y) (x = max(x, y))
#define smin(x, y) (x = min(x, y))

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)


using ll = long long;
using ld = long double;

template<typename T>
using vv = vector<vector<T>>;

using vi = vector<int>;
using ii = array<int, 2>;
using vii = vector<ii>;
using vvi = vv<int>;

using vll = vector<ll>;
using l2 = array<ll, 2>;
using vl2 = vector<l2>;
using vvll = vv<ll>;

template<typename T>
using minq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxq = priority_queue<T>;

template<typename T>
using oset = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

const ll M = 1000000007;
const ll infll = M * M;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<tuple<int, int, int>> tx;
    F0R(_, n) {
        int c, f, v;
        cin >> c >> f >> v;
        tx.eb(f, c, -v);
    }
    int m;
    cin >> m;
    F0R(_, m) {
        int c, f, v;
        cin >> c >> f >> v;
        tx.eb(f, -c, v);
    }
    sort(all(tx), greater<>());
    // dp[t][c] -> max value you can get with c spare cores
    // dp[t][c] = max(dp[t-1][c], dp[t-1][c-c[t]]
    int C = 50 * n + 1;
    vll dp(C, -infll);
    dp[0] = 0;
    F0R(t, n + m) {
        vll ndp(C, -infll);
        auto [f, tc, v] = tx[t];
        F0R(c, C) {
            if (dp[c] == -infll) continue;
            smax(ndp[c], dp[c]);
            if (0 <= c + tc && c + tc < C) smax(ndp[c+tc], dp[c]+v);
        }
        dp = ndp;
    }
    cout << *max_element(all(dp)) << '\n';
}

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