IQOverload

CF1000247F

Aug 14th, 2014
315
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None | 0 0
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <deque>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17. #include <vector>
  18.  
  19. #define fst first
  20. #define snd second
  21. #define all(x) (x).begin(), (x).end()
  22. #define clr(a, v) memset(a, v, sizeof(a))
  23. #define pb push_back
  24. #define mp make_pair
  25. #define sz(x) (int)(x.size())
  26. #define FORN(i,s,n) for(int i=s;i<(int)(n);i++)
  27. #define FOR(i,n) FORN(i,0,n)
  28. #define FORIT(i,x) for( typeof x.begin()  i=x.begin(); i!=x.end(); i++ )
  29. #define trace(x)    cerr << #x << ": " << x << endl;
  30. #define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  31.  
  32. using namespace std;
  33.  
  34. typedef long long int64;
  35. typedef vector <int> vi;
  36. typedef pair <int,int> ii;
  37. typedef vector <string> vs;
  38. typedef vector <ii> vii;
  39.  
  40. const int INF = 2e9+9;
  41.  
  42. vi A;
  43. int64 N,P,Q;
  44.  
  45. bool f ( int64 K ){
  46.     int64 T=K;
  47.     FOR(i,sz(A)){
  48.         int64 L=A[i];
  49.         int64 lo=0,hi=1e9+1,mi;
  50.         while(hi-lo>1){
  51.             mi=(hi+lo)/2;
  52.             if ( (mi*(P) + (K-mi)*Q) >=L ) hi=mi;
  53.             else lo=mi;
  54.         }
  55.         int64 ans;
  56.         if ( lo*(P) + (K-lo)*Q >=L ) ans=lo;
  57.         else ans=hi;
  58.         T-=ans;
  59.     }
  60.     if (T<0) return 0;
  61.     else return 1;
  62. }
  63.  
  64. int main(){
  65.     int64 aux;
  66.     cin>>N>>P>>Q;
  67.     A.assign(N,0);
  68.     FOR(i,N) scanf("%d", &A[i]);
  69.     int64 lo1=1,hi1=1e9+1,mi1,ans;
  70.     while(hi1-lo1>1){
  71.         mi1=(hi1+lo1)/2;
  72.         if (f(mi1))hi1=mi1;
  73.         else lo1=mi1;
  74.     }
  75.     if (f(lo1)) ans=lo1;
  76.     else ans=hi1;
  77.     cout<<ans<<endl;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment