제출 #646435

#제출 시각아이디문제언어결과실행 시간메모리
646435iulia13Cloud Computing (CEOI18_clo)C++14
72 / 100
551 ms1796 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 4005; const ll inf = 2e17; struct ura{ ll c, f, v; } a[N]; bool cmp (ura x, ura y) { return x.f > y.f; } ll n, m, mc; ll dp[2][N * 50]; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i].c >> a[i].f >> a[i].v; a[i].v *= -1; mc += 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 *= -1; } sort(a + 1, a + n + m + 1, cmp); for (int i = 1; i <= mc; i++) dp[0][i] = -inf; for (int i = 1; i <= n + m; i++) { for (int j = 0; j <= mc; j++) { dp[i % 2][j] = dp[1 - i % 2][j]; int pc = j - a[i].c; if (0 <= pc && pc <= mc && dp[1 - i % 2][pc] != inf) { dp[i % 2][j] = max(dp[i % 2][j], dp[1 - i % 2][pc] + a[i].v); } } } ll ans = 0; for (int i = 0; i <= mc; i++) ans = max(ans, dp[(n + m) % 2][i]); 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...