제출 #1022688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022688		eysbutno	Cloud Computing (CEOI18_clo)	C++17	100 / 100	847 ms	2156 KiB

clo

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = array<int, 2>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

template<class T> bool smax(T &a, T b) {
    return a < b ? a = b, 1 : 0;
}
template<class T> bool smin(T &a, T b) {
    return a > b ? a = b, 1 : 0;
}
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n; cin >> n;
    vector<array<int, 3>> ord;
    // {cores_added, freq, val_added}
    int tot = 0;
    for (int i = 0; i < n; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        ord.push_back({c, f, -v});
        tot += c;
    }
    int m; cin >> m;
    for (int i = 0; i < m; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        ord.push_back({-c, f, v});
    }
    sort(all(ord), [&](auto &i, auto &j) -> bool {
        return (i[1] == j[1]) ? i[2] < j[2] : i[1] > j[1]; 
    });
    const ll INF = 1e15;
    vector<ll> dp(tot + 1, -INF);
    dp[0] = 0;
    for (auto [c, f, v] : ord) {
        vector<ll> dp_t(tot + 1, -INF);
        for (int i = 0; i <= tot; i++) {
            int nxt = i + c;
            if (nxt >= 0 && nxt <= tot && dp[i] != -INF) { 
                smax(dp_t[nxt], dp[i] + v);
            }
            smax(dp_t[i], dp[i]);
        }
        dp = move(dp_t);
    }
    cout << *max_element(all(dp)) << "\n";
}
/**
 * Cloud Computing - CEOI 2018
 * The only constraint on the actual cores we
 * can give to certain orders are the frequencies
 * of the cores. Thus, we can sort both the orders
 * and the computers in order.
 * 
 * Then, because the sum of the cores is low, we knapsack
 * on the number of cores. Our DP state is the following:
 * dp[cores_used][cur_item] = most profit possible.
 */

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