Submission #1199987

#TimeUsernameProblemLanguageResultExecution timeMemory
1199987myst6Cloud Computing (CEOI18_clo)C++20
0 / 100
3097 ms55876 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll inf = 1LL << 60; void chmax(ll &a, ll b) { a = max(a, b); } int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector<int> C(n), F(n), V(n); for (int i=0; i<n; i++) cin >> C[i] >> F[i] >> V[i]; int m; cin >> m; vector<int> qC(m), qF(m), qV(m); for (int i=0; i<m; i++) cin >> qC[i] >> qF[i] >> qV[i]; vector<int> order(n); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&](int i, int j) -> bool { return F[i] < F[j]; }); vector<int> qOrder(m); iota(qOrder.begin(), qOrder.end(), 0); sort(qOrder.begin(), qOrder.end(), [&](int i, int j) -> bool { return qF[i] > qF[j]; }); vector dp(m+1, vector<ll>(50*n+1, -inf)); dp[0][0] = 0; for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { int jj = qOrder[j]; // add core on this row if (F[i] >= qF[jj]) { for (int k=50*n-C[i]; k>=0; k--) { chmax(dp[j][k+C[i]], dp[j][k] - V[i]); } } // take any subset onto the next row for (int k=0; k<=50*n; k++) { chmax(dp[j+1][k], dp[j][k]); } // take a subset and use it for (int k=qC[jj]; k<=50*n; k++) { chmax(dp[j+1][k-qC[jj]], dp[j][k] + qV[jj]); } } } // answer can be from any dp cell ll ans = -inf; for (int j=0; j<=m; j++) { for (int k=0; k<=50*n; k++) { chmax(ans, dp[j][k]); } } cout << ans << "\n"; 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...