fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/kG2wwm
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!