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. vector<int> adj[55],wth[N];
  10. vector<int>::iterator itr;
  11. ll solve(ll x,ll dis){
  12. 	if(x>=n){
  13. 		return 1;
  14. 	}
  15.  
  16. 	if(dp[x][dis]!=-1)
  17. 		return dp[x][dis];
  18.  
  19. 	ll mx=0;
  20. 	for(ll i=0;i<wth[x].size();i++){
  21. 		if(wth[x][i]==-1)
  22. 			continue;
  23. 		if(abs(a[x]-i)+dis<=k){
  24. 			mx=max(mx,solve(wth[x][i],abs(a[x]-i)+dis)+1);
  25. 		}else{
  26. 			mx=max(mx,1LL);
  27. 		}
  28. 	}
  29.  
  30. 	return dp[x][dis]=mx;
  31. }
  32.  
  33. int main()
  34. {
  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.     	adj[a[i]].push_back(i);
  41.     }
  42.     for(int i=1;i<=n;i++){
  43.     	for(int j=0;j<55;j++){
  44.     		if((adj[j]).size()==0){
  45.     			wth[i].push_back(-1);
  46.     			continue;
  47.     		}
  48.     		itr=upper_bound(adj[j].begin(),adj[j].end(),i);
  49.     		int idx;
  50.     		if(itr==adj[j].end())
  51.     			idx=-1;
  52.     		else
  53.     			idx=(*itr);
  54.     		// if(idx)
  55.     		wth[i].push_back(idx);
  56.     	}
  57.     }
  58.     if(k==0){
  59.         cout << "1\n";
  60.         return 0;
  61.     }
  62.     memset(dp,-1,sizeof(dp));
  63.     ll ans=solve(1,0);
  64.     if(ans==0)
  65.         ans++;
  66.     cout << ans << endl;
  67.     return 0;
  68. }
Success #stdin #stdout 0s 5392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/W7D64Z
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!