제출 #571898

#제출 시각아이디문제언어결과실행 시간메모리
571898piOOECloud Computing (CEOI18_clo)C++17
100 / 100
1674 ms1356 KiB
#include <bits/stdc++.h> using namespace std; #define sz(x) ((int)size(x)) #define all(x) begin(x), end(x) #define trace(x) cout << #x << ": " << (x) << endl; typedef long long ll; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; } const int N = 2000, C = 50; const ll infL = 3e18; ll dp[C * N + 1]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<array<int, 4>> a; for (int i = 0; i < n; ++i) { int c, f, v; cin >> c >> f >> v; a.push_back({f, 1, c, v}); } int m; cin >> m; int sum = N * C; for (int i = 0; i < m; ++i) { int c, f, v; cin >> c >> f >> v; a.push_back({f, 0, c, v}); } sort(all(a)); for (auto [f, t, c, v] : a) { if (t == 0) { for (int k = sum; k >= c; --k) { dp[k] = max(dp[k], dp[k - c] + v); } } else { for (int k = c; k <= sum; ++k) { dp[k - c] = max(dp[k - c], dp[k] - v); } } for (int k = 1; k <= sum; ++k) { dp[k] = max(dp[k], dp[k - 1]); } } cout << dp[0]; 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...