Submission #1218132

#TimeUsernameProblemLanguageResultExecution timeMemory
1218132johuthaCloud Computing (CEOI18_clo)C++20
100 / 100
354 ms2888 KiB
#include <algorithm> #include <iostream> #include <vector> #include <array> #define ll long long using namespace std; /* Sample: 4 4 2200 700 2 1800 10 20 2550 9999 4 2000 750 3 1 1500 300 6 1900 1500 3 2400 4550 */ const int C = 2000 * 50 + 1; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<array<ll,3>> transactions; for (int i = 0; i < n; i++) { ll c, f, v; cin >> c >> f >> v; transactions.push_back({f, c, -v}); } int m; cin >> m; for (int i = 0; i < m; i++) { ll c, f, v; cin >> c >> f >> v; transactions.push_back({f, -c, v}); } sort(transactions.rbegin(), transactions.rend()); int N = n + m; vector<vector<ll>> dp(2, vector<ll>(C, -1e18)); dp[0][0] = 0; for (int i = 0; i < N; i++) for (int j = 0; j < C; j++) { dp[(i + 1) & 1][j] = dp[i & 1][j]; if (j - transactions[i][1] >= 0 && j - transactions[i][1] < C) dp[(i + 1) & 1][j] = max(dp[(i+1) & 1][j], dp[i & 1][j - transactions[i][1]] + transactions[i][2]); } ll ans = 0; for (auto j: dp[N & 1]) ans = max(ans, j); cout << ans << "\n"; }
#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...