fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. const ll maxN = 1e5 + 36;
  6.  
  7. ll n, k;
  8. ll a[maxN];
  9. ll pref[maxN], suff[maxN];
  10.  
  11. void input() {
  12.     cin >> n >> k;
  13.     for (ll i = 1; i <= n; i++) {
  14.         cin >> a[i];
  15.     }
  16. }
  17.  
  18. void init() {
  19.     sort(a + 1, a + 1 + n);
  20. }
  21.  
  22. ll solve() {
  23.     // Calculate pref[i]: max elements that can be chosen in range [1, i]
  24.     ll l = 1;
  25.     for (ll i = 1; i <= n; i++) {
  26.         while (a[i] - a[l] > k) {
  27.             l++;
  28.         }
  29.         pref[i] = max(pref[i - 1], i - l + 1);
  30.     }
  31.  
  32.     // Calculate suff[i]: max elements that can be chosen in range [i, n]
  33.     ll r = n;
  34.     for (ll i = n; i >= 1; i--) {
  35.         while (a[r] - a[i] > k) {
  36.             r--;
  37.         }
  38.         suff[i] = max(suff[i + 1], r - i + 1);
  39.     }
  40.  
  41.     // Find max(pref[i] + suff[i + 1])
  42.     ll ans = 0;
  43.     for (ll i = 1; i <= n; i++) {
  44.         ans = max(ans, pref[i] + suff[i + 1]);
  45.     }
  46.     return ans;
  47. }
  48.  
  49. int main() {
  50.     ios_base::sync_with_stdio(0);
  51.     cin.tie(0); cout.tie(0);
  52.  
  53.     input();
  54.     init();
  55.     cout << solve() << "\n";
  56.  
  57.     return 0;
  58. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/WpMFtE
language:
C++14 (gcc 8.3)
created:
1 day 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!