fork(1) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/grWZlx
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!