Submission #1118996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118996		FubuGold	Cloud Computing (CEOI18_clo)	C++14	100 / 100	543 ms	2296 KiB

clo

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2000;
const int MAXV = 100000;
const long long INF = 2e18;
long long dp[2][MAXV+1];

struct Query {
    int c;
    long long f,v;
    bool operator < (const Query &qr) {
        if (f == qr.f) return c > qr.c;
        return f > qr.f;
    }
} qr[2*MAXN+1];

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n; cin >> n;
    for (int i=1;i<=n;i++) {
        cin >> qr[i].c >> qr[i].f >> qr[i].v;
        qr[i].v *= -1;
    }
    int m; cin >> m;
    for (int i=n+1;i<=n+m;i++) {
        cin >> qr[i].c >> qr[i].f >> qr[i].v;
        qr[i].c *= -1;
    }
    n += m;
    sort(qr+1,qr+n+1);
    for (int i=0;i<2;i++) {
        for (int j=0;j<=MAXV;j++) dp[i][j] = -INF;
    }
    dp[0][0] = 0;
    long long ans = 0;
    for (int i=1;i<=n;i++) {
//        cerr << qr[i].c << ' ' << qr[i].f << ' ' << qr[i].v << '\n';
        int cur = i & 1, pre = cur ^ 1;
        for (int j=0;j<=MAXV;j++) {
//            cerr << j << ' ' << cur << ' ' << pre << '\n';
            dp[cur][j] = dp[pre][j];
            if (j - qr[i].c >= 0 && j - qr[i].c <= MAXV) {
//                cerr << j - qr[i].c << '\n';
                dp[cur][j] = max(dp[cur][j],dp[pre][j - qr[i].c] + qr[i].v);
            }
//            if (dp[cur][j] > -1e9) cout << i << ' ' << j << ' ' << dp[cur][j] << '\n';
            if (i == n && j >= 0) ans = max(ans,dp[cur][j]);
        }
    }
    cout << ans;
    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