Submission #1091745

#TimeUsernameProblemLanguageResultExecution timeMemory
1091745gygCloud Computing (CEOI18_clo)C++17
36 / 100
705 ms3920 KiB
#pragma GCC optimize("Ofast", "unroll-loops") #pragma GCC target("avx2") #include <bits/stdc++.h> using namespace std; #define int long long #define arr array const int MX_N = 2e3 + 5, MX_M = 2e3 + 5, MX_C = 1e5 + 5, INF = 1e18; int n, m; struct Evnt { bool is_gn; int cp, pwr, vl; bool operator<(Evnt othr) { if (othr.pwr == pwr) return is_gn; return pwr > othr.pwr; } }; arr<Evnt, MX_N + MX_M> evnt; arr<arr<int, MX_C>, 2> dp; void cmp() { for (int i = 1; i <= 1e5; i++) dp[0][i] = -INF; for (int i = 1; i <= n + m; i++) { int prty = i % 2, opp_prty = (i + 1) % 2; dp[prty] = dp[opp_prty]; if (evnt[i].is_gn) { for (int c = 0; c <= 1e5; c++) if (c - evnt[i].cp >= 0) dp[prty][c] = max(dp[prty][c], dp[opp_prty][c - evnt[i].cp] - evnt[i].vl); } else { for (int c = 0; c <= 1e5; c++) if (c + evnt[i].cp <= 1e5) dp[prty][c] = max(dp[prty][c], dp[opp_prty][c + evnt[i].cp] + evnt[i].vl); } } } signed main() { // freopen("cld.in", "r", stdin); cin >> n; for (int i = 1; i <= n; i++) { int cp, pwr, vl; cin >> cp >> pwr >> vl; evnt[i] = {true, cp, pwr, vl}; } cin >> m; for (int i = 1; i <= m; i++) { int cp, pwr, vl; cin >> cp >> pwr >> vl; evnt[n + i] = {false, cp, pwr, vl}; } sort(evnt.begin() + 1, evnt.begin() + n + m + 1); cmp(); int ans = 0; for (int c = 0; c <= 1e5; c++) ans = max(ans, dp[(n + m) % 2][c]); cout << ans << endl; }
#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...