fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define ll long long
  5. #define F first
  6. #define S second
  7. typedef pair<ll,ll> ii;
  8. typedef pair<ll,ii> iii;
  9. bool isAll;
  10. ll n,m,bounty,increase,dmg;
  11. iii mons[200000],upd[200000];
  12. ll calc(ll t){
  13. ll mons_cur[200000];
  14. for(int i = 1;i<=n;i++){
  15. mons_cur[i] = min(mons[i].F,mons[i].S.F + t*mons[i].S.S);
  16. }
  17. for(int i = 1;i<=m;i++){
  18. ll time = upd[i].F;
  19. ll pos = upd[i].S.F;
  20. ll health = upd[i].S.S;
  21. if(time <= t){
  22. mons_cur[pos] = min(mons[pos].F,health + mons[pos].S.S*(t-time));
  23. }
  24. }
  25. ll sl = 0;
  26. for(int i = 1;i<=n;i++)if(mons_cur[i] <= dmg)sl++;
  27. if(sl == n) isAll = true;
  28. return sl * (bounty + t*increase);
  29. }
  30. int main()
  31. {
  32. cin >> n >> m;
  33. cin >> bounty >> increase >> dmg;
  34. bool bo = true;
  35. for(int i = 1;i<=n;i++){
  36. ll x,y,z; cin >> x >> y >> z;
  37. mons[i] = iii(x,ii(y,z));
  38. //if(dmg < x) bo = false;
  39. }
  40. for(int i = 1;i<=m;i++){
  41. ll x,y,z; cin >> x >> y >> z;
  42. upd[i] = iii(x,ii(y,z));
  43. }
  44. ll l = 1,r = round(1e15),cnt = 0;
  45. while(cnt <= 300){
  46. isAll = false;
  47. ll m1 = l + (r-l) / 3;
  48. ll m2 = r - (r-l) / 3;
  49. ll r1 = calc(m1),r2 = calc(m2);
  50. if(r1 < r2) l = m1; else r = m2;
  51. cnt++;
  52. if(!isAll) bo = false;
  53. }
  54. if(bo) cout << -1; else cout << calc((l+r)/2);
  55. //cout << calc(50);
  56. return 0;
  57. }
Success #stdin #stdout 0s 4524KB
stdin
Standard input is empty
stdout
-1