Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- #define sc 1000000
- using namespace std;
- ll N, U ;
- ll arr[100009] ;
- float dp[100009] ;
- bool mark = true ;
- float solve(ll idx, ll i, ll j, ll k)
- {
- if(idx == N)
- return 0 ;
- if(i != -1 && j != -1 && k != -1)
- {
- if(arr[k] - arr[i] > U)
- {
- return 0;
- }
- double p ;
- p = ((double)((1.0)*(arr[k]-arr[j])/(arr[k]-arr[i]))) * 1.0 ;
- return p ;
- }
- float ret = 0 ;
- if(i == -1)
- {
- ret = max(solve(idx+1, idx, j, k), solve(idx+1, i, j, k)) ;
- }
- else if(j == -1)
- {
- ret = max(solve(idx+1, i, idx, k), solve(idx+1, i, j, k)) ;
- }
- else if(k == -1)
- {
- ret = max(solve(idx+1, i, j, idx), solve(idx+1, i, j, k)) ;
- }
- return dp[idx] = ret ;
- }
- int main()
- {
- cin >> N >> U ;
- for(ll i = 0 ; i < N ; i++)
- {
- cin >> arr[i] ;
- }
- for(ll i = 0 ; i < 100001 ; i++)
- {
- dp[i] = -1 ;
- }
- float s ;
- s = solve(0, -1,-1,-1) ;
- if(s == 0)
- cout << -1 << endl ;
- else
- cout << s << endl ;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment