Submission #1118973

#TimeUsernameProblemLanguageResultExecution timeMemory
1118973FubuGoldCloud Computing (CEOI18_clo)C++14
72 / 100
532 ms2132 KiB
#include <bits/stdc++.h>

using namespace std;

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

struct Query {
    int c;
    long long f,v;
    bool operator < (const Query &qr) {
        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);
    memset(dp,-0x3f,sizeof(dp));
    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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...