Advertisement
knakul853

Untitled

Nov 7th, 2020
2,247
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.53 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/tree_policy.hpp>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/rope>
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7. using namespace __gnu_cxx;
  8.  
  9. #define mod 1000000007
  10.  /*
  11.     /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ *** Debugging Start *** \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
  12. */
  13. void __print(int x) {cerr << x;}
  14. void __print(long x) {cerr << x;}
  15. void __print(long long x) {cerr << x;}
  16. void __print(unsigned x) {cerr << x;}
  17. void __print(unsigned long x) {cerr << x;}
  18. void __print(unsigned long long x) {cerr << x;}
  19. void __print(float x) {cerr << x;}
  20. void __print(double x) {cerr << x;}
  21. void __print(long double x) {cerr << x;}
  22. void __print(char x) {cerr << '\'' << x << '\'';}
  23. void __print(const char *x) {cerr << '\"' << x << '\"';}
  24. void __print(const string &x) {cerr << '\"' << x << '\"';}
  25. void __print(bool x) {cerr << (x ? "true" : "false");}    
  26. template<typename T, typename V>
  27. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  28. template<typename T>
  29. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  30. void _print() {cerr << "]\n";}
  31. template <typename T, typename... V>
  32. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  33. #ifndef ONLINE_JUDGE
  34. #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
  35. #else
  36. #define debug(x...)
  37. #endif
  38. /*
  39.     /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ *** Debugging Ends *** \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
  40. */
  41. using namespace __gnu_pbds;
  42. template <typename T>
  43. using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  44.      
  45. /// Some frequent usable functions
  46. #define int                        long long
  47. void add(int &a,int b){a+=b;if(a>mod)a-=mod;}
  48. void sub(int &a,int b){a-=b;if(a<0)a+=mod;}
  49. void mul(int &a, int b) {a=1ll * a * b % mod;}
  50. template<typename T> T pow(T a,T b, long long m){T ans=1; while(b>0){ if(b%2==1) ans=(ans*a)%m; b/=2; a=(a*a)%m; } return ans%m; }
  51. int powmod(int a,int b)
  52. {int res = 1;while(b){if(b&1){res = (res * a)%mod;}b= b/2;a = (a*a)%mod;}return res;}
  53. int _ceil(int, int);
  54. int _floor(int a, int b) { return b < 0 ? _floor(-a, -b) : a < 0 ? -_ceil(-a, b) : a / b; }
  55. int _ceil(int a, int b) { return b < 0 ? _ceil(-a, -b) : a < 0 ? -_floor(-a, b) : (a + b - 1) / b; }
  56.      
  57. // int gcd(int a, int b, int &x, int &y) {if (a == 0) {x = 0; y = 1;return b;
  58. //     }int x1, y1;int d = gcd(b%a, a, x1, y1); x = y1 - (b / a) * x1;y = x1;return d;}
  59. // int find(int v){return v==parent[v]?v:parent[v] = find(parent[v]);}
  60. // void merge(int i,int j)
  61. //     {i = find(i);j = find(j);if(i == j)return;parent[parent[i]] = parent[j];cmp--;}
  62.      
  63. /*
  64.     /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ *** Directions in grids *** \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
  65. */
  66. // int dy[4] = {0,0,1,-1}, dx[4] = {1,-1,0,0}; // 4 Direction
  67. // int dx[] = {1,-1,0,0,1,1,-1,-1} , dy[] = {0,0,1,-1,1,-1,1,-1};  // 8 Direction
  68. // int dx[] = {1,-1,1,-1,2,2,-2,-2} , dy[] = {2,2,-2,-2,1,-1,1,-1};  // Knight moves
  69. // int dx[] = {2,-2,1,1,-1,-1} , dy[] = {0,0,1,-1,1,-1};  // Hexagonal Direction
  70. #pragma GCC target ("avx2")
  71. #pragma GCC optimization ("O3")
  72. #pragma GCC optimization ("unroll-loops")
  73. #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  74. #define sp(a , x) cout << fixed << setprecision(a) << x << endl;
  75. #define endl "\n"
  76. #define pb push_back
  77. #define pf push_front
  78. #define ub upper_bound
  79. #define lb lower_bound
  80. #define F first
  81. #define S second
  82. #define mset(a, b) memset(a, b, sizeof a)
  83. #define sz(x) ((int)(x.size()))
  84. #define sqr(x) ((x) * (x))
  85. #define graph vector<int>
  86. #define vi vector<int>
  87. #define vvi vector<vector<int>>
  88. #define pi pair<int,int>
  89. #define all(c)                      c.begin() , c.end()
  90. #define rep(i,a) for(int i=0;i<a;i++)
  91. #define rrep(i,a,b) for(int i=a;i>=b;i--)
  92. #define iter(it,a) for(auto it=a.begin();it!=a.end();it++)
  93. #define PQP priority_queue<pi, vector<pi>, greater<pi>>
  94. #define PQI priority_queue<int, vector<int>, greater<int>>
  95. #define dbg debug
  96. #define inf (int)1e18
  97. const long double EPS = 0.0000000001;
  98. const long double PI = 3.1415926535897932384;
  99. //vec.resize(unique(all(vec)) - vec.begin());
  100.  int dy[4] = {0,0,1,-1}, dx[4] = {1,-1,0,0};
  101.  
  102.  // Template Ends Here.
  103.      
  104.   /// define some data....... |
  105.  const int N = 30001;
  106.  
  107.  int dp[N];
  108.  map<int, int> mp;
  109.  
  110.  int f(int pre, int cur){
  111.  
  112.      if(cur >= N || cur < 0)
  113.          return 0;
  114.      int &ret = dp[cur];
  115.      if(ret != -1)
  116.          return ret;
  117.  
  118.      ret = 0;
  119.      int l = cur - pre;
  120.      int op1 = 0, op2 = 0, op3 = 0;
  121.  
  122.       if(mp.count(cur+l-1)){
  123.  
  124.           op1 = mp[cur+l-1] + f(cur, cur + l - 1);
  125.       }
  126.       op1 = max(op1, f(cur, cur + l - 1));
  127.  
  128.        if(mp.count(cur+l)){
  129.  
  130.           op2 = mp[cur+l] + f(cur, cur + l);
  131.       }
  132.       op2 = max(op2, f(cur, cur + l));
  133.  
  134.        if(mp.count(cur+l+1)){
  135.  
  136.           op3 = mp[cur+l+1] + f(cur, cur + l + 1);
  137.       }
  138.       op3 = max(op3, f(cur, cur + l + 1));
  139.      
  140.  
  141.       return ret = max({op1, op2, op3});
  142.  }
  143.  
  144.  void solve()
  145.  {
  146.      int n, d;
  147.      cin >> n >> d;
  148.      rep(i,n){
  149.          int x;
  150.          cin >> x;
  151.          mp[x]++;
  152.      }
  153.      mset(dp, -1);
  154.      
  155.      int ans = f(0, d);
  156.      if(mp.count(d))
  157.          ans++;
  158.      cout << ans << "\n";
  159.  }
  160.  
  161. int32_t main(){
  162.     fast;
  163.     int test = 1;
  164.     // cin >> test;
  165.     int tc = 1;
  166.     while (test--)
  167.     {
  168.         solve();
  169.     }
  170. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement