Submission #470849

#	Time	Username	Problem	Language	Result	Execution time	Memory
470849		cookiemonster04	Cloud Computing (CEOI18_clo)	C++17	100 / 100	488 ms	1988 KiB

clo

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define NINF -1000000000000000LL;
/* Date: 9/5/21
 * Link: https://oj.uz/problem/view/CEOI18_clo
 * Verdict: WA (72/100), AC
*/

struct Option {
    int c, f, v;
    Option(int _c, int _f, int _v) {
        c = _c; f = _f; v = _v;
    }
    inline bool operator<(const Option& o) {
        if (f != o.f) {
            return f > o.f;
        }
        return v < o.v;
    }
};
vector<Option> options;
LL dp[2][100005];

int N, M;
int main() {
    ios::sync_with_stdio(0);
    for (int i = 0; i < 100005; i++) {
        dp[0][i] = NINF;
        dp[1][i] = NINF;
    }
    cin >> N;
    for (int i = 0; i < N; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        options.push_back(Option(c, f, -v));
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
        int c, f, v;
        cin >> c >> f >> v;
        options.push_back(Option(-c, f, v));
    }
    sort(options.begin(), options.end());
    int crow = 0;
    int rrow = 1;
    const int len = N+M;
    dp[0][0] = 0;
    for (int i = 0; i < len; i++) {
        const int cc = options[i].c;
        const int cv = options[i].v;
        const int lim = min(100000, 100000+cc);
        const int start = max(0, cc);
        for (int j = start; j <= lim; j++) {
            dp[rrow][j] = max(dp[crow][j], dp[crow][j-cc]+cv);
        }
        for (int j = 0; j < start; j++) {
            dp[rrow][j] = dp[crow][j];
        }
        for (int j = lim+1; j <= 100000; j++) {
            dp[rrow][j] = dp[crow][j];
        }
        crow = rrow;
        rrow = 1 ^ rrow;
    }
    LL ans = 0;
    for (int i = 0; i <= 100000; i++) {
        ans = max(ans, dp[crow][i]);
    }
    cout << ans << endl;
}

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