Submission #1019505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019505		aufan	Cloud Computing (CEOI18_clo)	C++17	100 / 100	258 ms	1372 KiB

clo

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int inff = 1e18;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n;
        cin >> n;

        vector<array<int, 4>> a;
        for (int i = 0; i < n; i++) {
                int c, f, v;
                cin >> c >> f >> v;
                
                a.push_back({c, f, v, 0});
        }

        int m;
        cin >> m;

        for (int i = 0; i < m; i++) {
                int c, f, v;
                cin >> c >> f >> v;

                a.push_back({c, f, v, 1});
        }

        sort(a.begin(), a.end(), [&](auto x, auto y) {
                if (x[1] == y[1]) return x[3] < y[3];
                return x[1] > y[1];
        });

        vector<int> dp(50 * n + 1, -inff);
        dp[0] = 0;
        for (auto [c, f, v, t] : a) {
                if (t == 0) {
                        for (int i = 50 * n; i - c >= 0; i--) {
                                dp[i] = max(dp[i], dp[i - c] - v);
                        }
                } else if (t == 1) {
                        for (int i = 0; i + c <= 50 * n; i++) {
                                dp[i] = max(dp[i], dp[i + c] + v);
                        }
                }
        }

        int ans = 0;
        for (int i = 0; i <= 50 * n; i++) ans = max(ans, dp[i]);

        cout << ans << '\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