Submission #1090583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090583		EmmaXII	Cloud Computing (CEOI18_clo)	C++17	100 / 100	287 ms	1624 KiB

clo

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;

#define all(x) x.begin(), x.end()
#define ckmin(a,b) a = min(a,b)
#define ckmax(a,b) a = max(a,b)

struct Computer {
    int c;
    ll f;
    ll v;
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N;
    cin >> N;
    vector<Computer> store(N);
    for (int i=0;i<N;i++) cin >> store[i].c >> store[i].f >> store[i].v;
    
    int M;
    cin >> M;
    vector<Computer> orders(M);
    for (int i=0;i<M;i++) cin >> orders[i].c >> orders[i].f >> orders[i].v;

    using Event = tuple<ll, int, ll>;
    vector<Event> events;
    for (int i=0;i<N;i++) {
        events.push_back({store[i].f, store[i].c, -store[i].v});
    }
    for (int i=0;i<M;i++) {
        events.push_back({orders[i].f, -orders[i].c, orders[i].v});
    }

    sort(all(events));
    reverse(all(events));

    int E = (int)events.size();
    int maxC = 50*N;
    // vvll dp(E+1, vll(maxC + 1, -1e18));
    vll dp(maxC + 1, -1e18);
    dp[0] = 0;
    // dp[0][0] = 0;
    for (int i=0;i<E;i++) {
        auto [f, c, v] = events[i];
        if (c > 0) {
            // store
            // for (int cp=0;cp+c<=maxC;cp++) {
            //     ckmax(dp[i+1][cp+c], dp[i][cp] + v);
            // }
            for (int cp=maxC-c;cp>=0;cp--) {
                ckmax(dp[cp+c], dp[cp] + v);
            }
        } else {
            // order
            // for (int cp=-c;cp<=maxC;cp++) {
            //     ckmax(dp[i+1][cp+c], dp[i][cp] + v);
            // }
            for (int cp=-c;cp<=maxC;cp++) {
                ckmax(dp[cp+c], dp[cp] + v);
            }
        }
        // can also ignore i
        // for (int cp=0;cp<=maxC;cp++) ckmax(dp[i+1][cp], dp[i][cp]);
    }

    ll ans = 0;
    // for (int c=0;c<=maxC;c++) ckmax(ans, dp[E][c]);
    for (int c=0;c<=maxC;c++) ckmax(ans, dp[c]);

    cout << ans << endl;

    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