Submission #1265296

#TimeUsernameProblemLanguageResultExecution timeMemory
1265296dxfCloud Computing (CEOI18_clo)C++17
100 / 100
318 ms1484 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; typedef long long ll; #define change_io() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define el endl #define all(x) begin(x), end(x) #define pb push_back #define mp make_pair #define INF 1000000005 #define LLINF 1e18 #define MOD 1000000007 #define MOD9 998244353 // remove single val from multiset with -> os.find_by_order(os.order_of_key(x)) typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; typedef tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pair_set; const ll N5 = 1e5 + 5; const ll N6 = 1e6 + 5; const ll NN5=2e5+5; const ll N3=1e3+5; #define dtrap cout << "catch" << el; /*goofball behavior * initialize dps correctly: 0, -INF, INF * change lb and ub for binary search back after making bounds smaller for debugging * check mod in problem statement */ const int MAXDIM = N6; ll dp[MAXDIM]; void solve() { int n; cin >> n; ll total_cores = 0; vector<array<ll, 4>> cc; for (int i = 0; i < n; ++i) { ll c,f,v; cin >> c >> f >> v; cc.pb({-1*f, 0, c, v}); total_cores += c; } int m; cin >> m; for (int i = 0; i < m; ++i) { ll c,f,v; cin >> c >> f >> v; cc.pb({-1*f,1, c, v}); } //assign INF for (int j = 0; j <= total_cores; ++j) { dp[j] = -1*LLINF; } dp[0] = 0; sort(all(cc)); for (int i = 0; i < n+m; ++i) { auto& itm = cc[i]; if (itm[1] == 0) { for (int j = total_cores; j >= 0; j--) { if (j-itm[2] < 0) continue; dp[j] = max(dp[j], dp[j-itm[2]]-itm[3]); } } else { for (int j = 0; j <= total_cores; ++j) { if (j+itm[2] > total_cores) continue; dp[j] = max(dp[j], dp[j+itm[2]]+itm[3]); } } } ll ans = 0; for (int i = 0; i <= total_cores; ++i) { ans = max(ans, dp[i]); } cout<<ans<<"\n"; } int main() { //freopen("problemname.in", "r", stdin); //freopen("problemname.out", "w", stdout); change_io(); ll T; T=1; //cin>>T; while (T--) { solve(); } 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...