Submission #991897

#	Time	Username	Problem	Language	Result	Execution time	Memory
991897		crafticat	Cloud Computing (CEOI18_clo)	C++17	100 / 100	923 ms	2256 KiB

clo

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using tup = tuple<ll,ll,ll>;

ll n, q;
ll MAX_SUM = 0;
constexpr ll inf = 1e18;

vector<ll> solve(vector<tup> &data, bool mex) {
    vector<ll> dp(vector<ll>(MAX_SUM + 1,mex ? -inf : inf));
    dp[0] = 0;

    for (ll i = 1; i <= data.size() ; ++i) {
        vector<ll> newDp = dp;
        auto [f,c, v] = data[i - 1];
        for (ll j = 0; j <= MAX_SUM; ++j) {
            if (mex) {
                if (j - c >= 0 && j - c <= MAX_SUM) newDp[j] = max(dp[j],dp[j - c] + v);
            } else {
                if (j - c >= 0 && j - c <= MAX_SUM) newDp[j] = min(dp[j],dp[j - c] + v);
            }
        }
        dp = newDp;
    }

    return dp;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n;
    vector<tup> arr;
    ll s1 = 0, s2 = 0;
    for (ll i = 0; i < n; ++i) {
        ll c, f, v; cin >> c >> f >> v;
        arr.emplace_back(f,c,-v);
        s1 += c;
    }

    cin >> q;
    for (ll i = 0; i < q; ++i) {
        ll c, f, v; cin >> c >> f >> v;
        arr.emplace_back(f,-c,v);
        s2 += c;
    }
    MAX_SUM = max(s2, s1);
    std::sort(arr.begin(), arr.end());
    std::reverse(arr.begin(), arr.end());

    auto c = solve(arr, true);

    ll ans = 0;
    for (ll i = 0; i <= MAX_SUM; ++i) {
        ans = max(c[i],ans);
    }

    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

clo.cpp: In function 'std::vector<long long int> solve(std::vector<std::tuple<long long int, long long int, long long int> >&, bool)':
clo.cpp:15:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (ll i = 1; i <= data.size() ; ++i) {
      |                    ~~^~~~~~~~~~~~~~

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