fork download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <string.h>
  4. using namespace std;
  5.  
  6. int cnt[30001];
  7. int dp[30001][2];
  8.  
  9. int main() {
  10. 	int n,d;
  11. 	memset(cnt,0,sizeof(cnt));
  12. 	for(int i=0; i<30000; i++)
  13. 		dp[i][0] = (dp[i][1] = 0);
  14. 	scanf("%d%d",&n,&d);
  15. 	for(int i=0; i<n; i++) {
  16. 		int num;
  17. 		cin>>num;
  18. 		cnt[num]++;
  19. 	}
  20. 	dp[d][0]=d;
  21. 	dp[d][1]=cnt[d];
  22. 	for(int i=d; i<30001; i++) {
  23. 		if(dp[i][0]==0)
  24. 			continue;
  25. 		dp[i][1] += cnt[i];
  26. 		if(dp[i][0]+i<30001) {
  27. 			dp[i+dp[i][0]][0] = i+dp[i][0];
  28. 			dp[i+dp[i][0]][1] = dp[i][1];
  29. 		}
  30. 		if(dp[i][0]+i+1<30001) {
  31. 			dp[i+dp[i][0]+1][0] = i+dp[i][0]+1;
  32. 			dp[i+dp[i][0]+1][1] = dp[i][1];
  33. 		}
  34. 		if(dp[i][0]+i-1<30001) {
  35. 			dp[i+dp[i][0]-1][0] = i+dp[i][0]-1;
  36. 			dp[i+dp[i][0]-1][1] = dp[i][1];
  37. 		}
  38. 	}
  39.  
  40. 	int max=0;
  41. 	for(int i=0; i<30001; i++)
  42. 		if(dp[i][1]>max)
  43. 			max = dp[i][1];
  44. 	cout<<max<<endl;
  45. 	return 0;
  46. }
Success #stdin #stdout 0s 3496KB
comments (?)
stdin
copy 
8 8
9
19
28
36
45
55
66
78
stdout
copy 
1
https://ideone.com/OFoU5G
Some DP code
language:
C++ (gcc 8.3)
created:
9 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!