0
Your rating: None

CodeChef submission 107789 (C++ 4.0.0-8)

CodeChef submission 107789 (C++ 4.0.0-8) plaintext list. Status: AC, problem H2, contest OCT09. By braineater (Harpreet Singh), 2009-10-10 20:47:43.
  1. #include <cstdio>
  2. #include <vector>
  3. #include <cmath>
  4. #include <cassert>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. double m;
  9. int S[110000], W[110000];
  10. double A[110000];
  11.  
  12. int main()
  13. {
  14.   int N;
  15.   scanf("%d", &N);
  16.   
  17.   for(int i=0; i<N; i++){
  18.     scanf("%d %d", &W[i], &S[i]);
  19.   }
  20.   
  21.   double l=0, r=10;
  22.   while(r-l>2e-6){
  23.     m = (l+r)/2;
  24.     bool cando=true;
  25.     for(int i=0; i<N; i++){
  26.       A[i] = S[i]-m*W[i];
  27.     }
  28.    
  29.     sort(A, A+N);
  30.     for(int i=0; 2*i<N; i++){
  31.       if(A[i]+A[N-i-1]<20*m) 
  32. 	cando = false;
  33.     }
  34.  
  35.     if(cando) l=m;
  36.     else r=m;
  37.   }
  38.   printf("%lf\n", m);
  39.   return 0;
  40. }
  41.

Comments