ulvis.paste.net

ulvis.paste.net

Paste Search Dynamic
Recent pastes
solve
  1. #include <bits/stdc++.h>`
  2.  
  3. #define slld(longvalue) scanf("%lld", &longvalue)
  4.  
  5. #define ll long long
  6.  
  7. #define mnlld -LLONG_MAX
  8.  
  9.  
  10. using namespace std;
  11.  
  12. ll dp[30005][550];
  13. ll mp[30005];
  14. ll d;
  15.  
  16. ll solve(ll cur, ll jump)
  17. {
  18.  
  19.     if(cur > 30000 || jump == 0) return 0;
  20.  
  21.     ll flag = jump - d;
  22.     flag += 250;
  23.  
  24.      if(dp[cur][flag] != -1) return dp[cur][flag];
  25.  
  26.     ll cnt = 0;
  27.     if(jump-1!=0)
  28.         cnt = max(cnt, solve(cur + jump-1, jump - 1));
  29.     cnt = max(cnt, solve(cur + jump+1, jump + 1));
  30.     cnt = max(cnt, solve(cur + jump, jump));
  31.  
  32.     cnt += mp[cur];
  33.  
  34.     return dp[cur][flag] = cnt;
  35. }
  36.  
  37. int main()
  38. {
  39.     ll i, j, k, l, m, n, o;
  40.     ll testcase;
  41.     ll input, flag, tag, ans;
  42.  
  43. //    freopen("in.txt", "r", stdin);
  44.  
  45.     memset(dp,-1,sizeof dp);
  46.     memset(mp,0,sizeof mp);
  47.  
  48.     slld(n);
  49.     slld(d);
  50.  
  51.     for(i = 1; i <= n; i++)
  52.     {
  53.         slld(input);
  54.  
  55.         mp[input]++;
  56.     }
  57.  
  58.     //cout << 6;
  59.     ans = solve(d,d);
  60.     //cout << 5;
  61.  
  62.     cout << ans << endl;
  63.  
  64.  
  65. }
  66.  
  67.  
  68.  
  69.  
Parsed in 0.008 seconds