fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4.  
  5. const ll N = 1e5+5;
  6.  
  7.  
  8. ll n,k,dp[N][55],a[N];
  9.  
  10. ll solve(ll x,ll dis){
  11. if(x>=n){
  12. return 1;
  13. }
  14.  
  15. if(dp[x][dis]!=-1)
  16. return dp[x][dis];
  17.  
  18. ll mx=0,fre[55]={0};
  19. for(ll i=x+1;i<=n;i++){
  20. if(abs(a[x]-a[i])+dis<=k && (!fre[a[i]])){
  21. mx=max(mx,solve(i,abs(a[x]-a[i])+dis)+1);
  22.  
  23. }else{
  24. mx=max(mx,1LL);
  25. }
  26. fre[a[i]]=1;
  27. }
  28.  
  29. return dp[x][dis]=mx;
  30. }
  31.  
  32. int main()
  33. {
  34. // freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
  35. ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  36. cin >> n >> k;
  37.  
  38. for(int i=1;i<=n;i++)
  39. cin >> a[i];
  40. if(k==0){
  41. cout << "1\n";
  42. return 0;
  43. }
  44. memset(dp,-1,sizeof(dp));
  45. ll ans=solve(1,0);
  46. if(ans==0)
  47. ans++;
  48. cout << ans << endl;
  49. return 0;
  50. }
Success #stdin #stdout 0s 4480KB
stdin
Standard input is empty
stdout
1