fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pii pair<int , int>
  4. #define ll long long
  5. #define mp make_pair
  6. #define pb push_back
  7. bool check(vector<int> &p, vector<int> &m, ll &total_cost, ll level){
  8.     ll total = 0;
  9.     for(int i = 0 ; i < p.size() ; i++){
  10.         ll diff = level - p[i];
  11.         if(diff > 0)
  12.             total += diff*(ll)m[i];
  13.         if(total > total_cost)
  14.             return false;
  15.     }
  16.     return true;
  17. }
  18. ll b_search(vector<int> &p, vector<int> &m , ll total_cost){
  19.     ll low = 0 , high = (LLONG_MAX/10), mid , ans = -1;
  20.     while(low < high){
  21.         mid = (low + high) >> 1;
  22.         if(check(p, m, total_cost , mid)){
  23.             low = mid+1;
  24.             ans = max(mid , ans);
  25.         } else high = mid;
  26.     }
  27.     return ans;
  28. }
  29. int main(){
  30.     int t;
  31.     scanf("%d",&t);
  32.     while(t--){
  33.         ll n , total_cost;
  34.         scanf("%lld%lld", &n , &total_cost);
  35.         vector<int> p(n) , m(n);
  36.         for(int i = 0 ; i < n ; i++){
  37.             scanf("%d%d" , &p[i] , &m[i]);
  38.         }
  39.         printf("%lld\n" , b_search(p , m , total_cost));
  40.     }
  41.     return 0;
  42. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
1 
5 1000000000000 
1 1000000000 
1 1000000000 
1 1000000000 
1 1000000000 
1000000000 1
stdout
copy 
28149731449694
https://ideone.com/wOLsFC
language:
C++ (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!