fork download
copy 
  1.  
  2. // author : jeetu86044
  3.  
  4. #include<bits/stdc++.h>
  5. #include<stdio.h>
  6. using namespace std;
  7. #define ll long long int
  8. void MergeSort(ll *p,ll *q,ll low,ll high,ll min);
  9. void Merge(ll *p,ll *q,ll low,ll mid,ll high,ll min);
  10. ll ciel(long double n);
  11. int main(){
  12. ll n,in[1000000],rt[1000000],req,min,re=9223372036854775807,count=0,sum1=0,sum=0,count1,diff,sum3=0,flag=0,i;
  13. long double x=1.0000000000000000000;
  14. scanf("%lld%lld%lld",&n,&req,&min);
  15.  
  16. for(i=0;i<n;i++){
  17.     scanf("%lld%lld",&in[i],&rt[i]);
  18. }
  19.  MergeSort(in,rt,0,n-1,min);
  20.  for(i=n-1;i>=0;i--){
  21.     count1=ciel((long double)(min-in[i])/(rt[i]*x));
  22.     /****************************
  23.      *         BUG FIX          *
  24.      *  if(count1<0) count1=0;  *
  25.      ****************************/
  26.    // printf("%lld re\n",re);
  27.     diff=count1-count;
  28.     if(count1>=re){
  29.         printf("%lld\n",re);
  30.         flag=1;
  31.         break;
  32.     }
  33.    sum=(count1*rt[i]+in[i])+sum1*diff+sum;
  34.    sum1=sum1+rt[i];
  35.    sum3=sum3+in[i];
  36.    if(sum>=req){
  37.     printf("%lld\n",count1);
  38.     flag=1;
  39.            break;
  40.    }
  41.    else{
  42.     re=ciel((long double)(req-sum3)/(sum1*x));
  43.     count=count1;
  44.    }
  45.  
  46.  
  47.  }
  48. if(!flag)
  49.     printf("%lld\n",re);
  50.  
  51. return 0;
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58. }
  59. ll ciel(long double n){
  60. ll n1;
  61. long double x=0.00000000000000000000;
  62. n1=n;
  63. n=n-n1;
  64. if(n==x)
  65.     return n1;
  66. else return (n1+1);
  67.  
  68.  
  69.  
  70. }
  71.  
  72.  
  73. void MergeSort(ll *p,ll *q,ll low,ll high,ll min){
  74.    ll mid;
  75. if(low<high){
  76.     mid=(low+high)/2;
  77.     MergeSort(p,q,low,mid,min);
  78.     MergeSort(p,q,mid+1,high, min);
  79.     Merge(p,q,low,mid,high,min);
  80. }
  81.  
  82.  
  83. }
  84. void Merge(ll *p,ll *q,ll low,ll mid,ll high,ll min){
  85. ll k,i,j,b[1000000],c[1000000];
  86. long double x,y,z=1.000000000000000;
  87. i=low,j=mid+1,k=0;
  88. while(i<=mid&&j<=high){
  89.         x=(*(p+i)-min)/( *(q+i)*z);
  90.    y=(*(p+j)-min)/( *(q+j)*z);
  91.     if(x<y){
  92.        b[k]=*(p+i);
  93.        c[k]=*(q+i);
  94.        i++,k++; }
  95.        else{
  96.         b[k]=*(p+j);
  97.         c[k]=*(q+j);
  98.         j++,k++;
  99.        }
  100. }
  101. while(i<=mid){
  102.         b[k]=*(p+i);
  103.         c[k]=*(q+i);
  104.         i++,k++;
  105.        }
  106. while(j<=high){
  107.         b[k]=*(p+j);
  108.         c[k]=*(q+j);
  109.         j++,k++;
  110.        }
  111. for(i=low,j=0;i<=high;i++,j++){
  112.     *(p+i)=b[j];
  113.     *(q+i)=c[j];
  114.  
  115. }
  116.  
  117. }
  118.  
  119.  
Success #stdin #stdout 0s 31568KB
comments (?)
stdin
copy 
1 2 2
4 1

ANOTHER BUG:
1 1 1
2 2
Output is 1, should be 0
stdout
copy 
-2
https://ideone.com/QqsJ0z
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!