shamiul93

C

Mar 24th, 2018
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.20 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define sc 1000000
  4.  
  5. using namespace std;
  6.  
  7. ll N, U ;
  8.  
  9. ll arr[100009] ;
  10. float dp[100009] ;
  11. bool mark = true ;
  12.  
  13. float solve(ll idx, ll i, ll j, ll k)
  14. {
  15.     if(idx == N)
  16.         return 0 ;
  17.  
  18.     if(i != -1 && j != -1 && k != -1)
  19.     {
  20.         if(arr[k] - arr[i] > U)
  21.         {
  22.             return 0;
  23.         }
  24.  
  25.         double p ;
  26.         p = ((double)((1.0)*(arr[k]-arr[j])/(arr[k]-arr[i]))) * 1.0 ;
  27.  
  28.  
  29.         return  p ;
  30.     }
  31.  
  32.     float ret = 0 ;
  33.  
  34.     if(i == -1)
  35.     {
  36.         ret = max(solve(idx+1, idx, j, k), solve(idx+1, i, j, k)) ;
  37.     }
  38.     else if(j == -1)
  39.     {
  40.         ret = max(solve(idx+1, i, idx, k), solve(idx+1, i, j, k)) ;
  41.  
  42.     }
  43.     else if(k == -1)
  44.     {
  45.         ret = max(solve(idx+1, i, j, idx), solve(idx+1, i, j, k)) ;
  46.  
  47.     }
  48.  
  49.     return dp[idx] = ret  ;
  50.  
  51. }
  52.  
  53. int main()
  54. {
  55.     cin >> N >> U ;
  56.  
  57.  
  58.     for(ll i = 0 ; i < N  ; i++)
  59.     {
  60.         cin >> arr[i] ;
  61.     }
  62.  
  63.  
  64.     for(ll i = 0 ; i < 100001 ; i++)
  65.     {
  66.         dp[i] = -1 ;
  67.     }
  68.  
  69.  
  70.     float s ;
  71.  
  72.     s = solve(0, -1,-1,-1) ;
  73.  
  74.     if(s == 0)
  75.         cout << -1 << endl ;
  76.     else
  77.         cout << s << endl  ;
  78.  
  79.  
  80.     return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment