Submission #1292566

#TimeUsernameProblemLanguageResultExecution timeMemory
1292566duongquanghai08Cloud Computing (CEOI18_clo)C++20
0 / 100
1 ms572 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 2002;
const int M = 100002;
const long long inf = 1e18 + 7;
struct Data {
    int c, f, v;
}a[2 * N];
int n, m;
long long dp[2][M];
void Solve() {
    cin >> n;
    int S = 0;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].c >> a[i].f >> a[i].v;
        a[i].v = -a[i].v;
        S += a[i].c;
    }
    cin >> m;
    for(int i = n + 1; i <= n + m; i++) {
        cin >> a[i].c >> a[i].f >> a[i].v;
        a[i].c = -a[i].c;
    }
    n += m;
    sort(a + 1, a + n + 1, [&] (Data A, Data B) {
         if(A.f == B.f) return A.c > B.c;
         return A.f > B.f;
    });
    int pre = 0, cur = 1;
    for(int i = 0; i <= S; i++) dp[pre][i] = -inf;
    dp[pre][0] = 0;
    for(int i = 1; i <= n; i++) {
        cout << a[i].c << " " << a[i].f << " " << a[i].v << '\n';
        for(int j = 0; j <= S; j++) dp[cur][j] = -inf;
        for(int j = 0; j <= S; j++) {
            dp[cur][j] = max(dp[cur][j], dp[pre][j]);
            int nxt_j = j + a[i].c;
            if(nxt_j < 0 || nxt_j > S || dp[pre][j] == -inf) continue;
            dp[cur][nxt_j] = max(dp[cur][nxt_j], dp[pre][j] + a[i].v);
        }
        swap(pre, cur);
    }
    long long ans = 0;
    for(int i = 0; i <= S; i++) ans = max(ans, dp[pre][i]);
    cout << ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    Solve();
}
#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...