fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int const NMAX = 5e4;
  6. int n, k;
  7. int a[1 + NMAX];
  8. int le[1 + NMAX], ri[1 + NMAX];
  9. int maxL[1 + NMAX], maxR[1 + NMAX];
  10.  
  11. int main() {
  12.     cin >> n >> k;
  13.     for(int i = 1; i <= n; i++) {
  14.         cin >> a[i];
  15.     }
  16.     sort(a+1, a+n+1);
  17.     int to = 1;
  18.     for(int i = 1; i <= n; i++) {
  19.         while(to < n && a[to+1]-a[i] <= k) {
  20.             to++;
  21.         }
  22.         ri[i] = to;
  23.     }
  24.     int from = n;
  25.     for(int i = n; i >= 1; i--) {
  26.         while(from > 1 && a[i]-a[from-1] <= k) {
  27.             from--;
  28.         }
  29.         le[i] = from;
  30.     }
  31.     for(int i = 1; i <= n; i++) {
  32.         maxL[i] = max(maxL[i-1], i-le[i]+1);
  33.     }
  34.     for(int i = n; i >= 1; i--) {
  35.         maxR[i] = max(maxR[i+1], ri[i]-i+1);
  36.     }
  37.     int ans = 0;
  38.     for(int i = 1; i < n; i++) {
  39.         ans = max(ans, maxL[i] + maxR[i+1]);
  40.         //cout << i << ": " << le[i] << ", " << ri[i] << "\n";
  41.     }
  42.     cout << ans << "\n";
  43. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
5 3
10
6
3
3
4
stdout
copy 
5
https://ideone.com/rFDBxe
language:
C++14 (gcc 8.3)
created:
5 days 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!