Submission #1285761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285761		domi	Cloud Computing (CEOI18_clo)	C++20	100 / 100	268 ms	1472 KiB

clo

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "Yes" << endl; return; }
#define NO { cout << "No" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;
using tii = std::tuple<int, int, int, int>;

const int NMAX = 2e3;
const int SIZE = 1e5;
const int INF = 1e16;

using namespace std;

vector<tii>obj;
vector<tii>ord;
int dp[SIZE + 5], n, m;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;

    obj.resize(n);
    for (int i = 0, c, f, v; i < n; ++i) {
        cin >> c >> f >> v;
        obj[i] = {f, 1, c, v};
    }

    cin >> m;
    ord.resize(m);
    for (int i = 0, c, f, v; i < m; ++i) {
        cin >> c >> f >> v;
        ord[i] = {f, 0, c, v};
    }

    sort(all(obj), std::greater());
    sort(all(ord), std::greater());
    vector<tii>all;
    all.resize(n + m);
    std::merge(all(obj), all(ord), all.begin(), std::greater());

    fill(dp + 1, dp + SIZE + 1, -INF);
    for (auto &[f, type, c, v] : all) {
        if (type == 0) {
            for(int i = 0; i + c <= SIZE; ++i)
                dp[i] = max(dp[i], dp[i + c] + v);
        }

        if (type == 1) {
            for(int i = SIZE - c; i >= 0; --i)
                dp[i + c] = max(dp[i + c], dp[i] - v);
        }
    }

    cout << *max_element(dp, dp + SIZE + 1) << '\n';
    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