fork download
copy 
  1. /*
  2.      /\_/\
  3.     (= ._.)
  4.     / >0  \>1
  5.  
  6. */
  7. #include<bits/stdc++.h>
  8. using namespace std;
  9. #define fi first
  10. #define se second
  11. #define ull unsigned long long
  12. #define int long long
  13. #define endl '\n'
  14. #define pb push_back
  15. #define pf push_front
  16. #define pii pair<int,int>
  17. #define pll pair<int64_t,int64_t>
  18. #define sz(x) (int32_t)(x).size()
  19. #define all(x) (x).begin(),(x).end()
  20. #define f0(i,n) for(int32_t i=0;i<n;i++)
  21. #define f1(i,n) for(int32_t i=1;i<=n;i++)
  22. #define fz(i,a,n,z) for(int32_t i=a;i<n;i+=z)
  23. #define rep(i,a,n,z) for(int32_t i=a;i>n;i-=z)
  24. #define onii_chan ios_base::sync_with_stdio(false);
  25. #define baka cin.tie(0);
  26. #define hentai cout.tie(0);
  27. #define file(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
  28. template <typename T>
  29. using heap = priority_queue<T, vector<T>, greater<T>>;
  30. template <typename T>
  31. using priq = priority_queue<T>;
  32. template<typename... T>
  33. void in(T&... args) { ((cin >> args), ...); }
  34. template<typename F, typename... R>
  35. void print(int ok, F&& f, R&&... r) {
  36.     static bool space = true;
  37.     if (ok == 2) {
  38.         cout << f << '\n';
  39.         ((cout << r << '\n'), ...);
  40.         return;
  41.     }
  42.     if (ok) {
  43.         if (!space) cout << " ";
  44.         space = false;
  45.     }
  46.     cout << f;
  47.     ((cout << " " << r), ...);
  48.     if (ok == 3) {
  49.         cout << '\n';
  50.         space = true;
  51.     }
  52. }
  53. template <typename T>
  54. bool minimize(T& a, const T& b) {
  55.     return b < a ? (a = b, true) : false;
  56. }
  57. template <typename T>
  58. bool maximize(T& a, const T& b) {
  59.     return a < b ? (a = b, true) : false;
  60. }
  61. const int MAXN = 1e6;
  62. const int mod = 1e9 + 7;
  63. const int base = 131;
  64. const int INF = LLONG_MAX;
  65. inline void add(int &a,int b){
  66.     a += b;
  67.     if(a >= mod) a -= mod;
  68.     if(a < 0) a += mod;
  69. }
  70. ///---------------------------------------------------------------
  71. /// End the template, take a sip of Coke before reading the code
  72. int n,k,a[MAXN + 5];
  73. void inp(void){
  74.     cin>>n>>k;
  75.     for(int i = 1; i <= n; i++){
  76.         cin>>a[i];
  77.     }
  78. }
  79. namespace subtask_1{
  80.     int mask[15], ans = 0;
  81.     void recursion(int pos){
  82.         if(pos > n){
  83.             int cnt = 0;
  84.             vector<int>one;
  85.             vector<int>two;
  86.             for(int i = 1; i <= n; i++){
  87.                 if(mask[i] == 1){
  88.                     one.pb(a[i]);
  89.                     ++cnt;
  90.                 }
  91.                 else if(mask[i] == 2){
  92.                     two.pb(a[i]);
  93.                     ++cnt;
  94.                 }
  95.             }
  96.             if(one.empty()|| two.empty())return;
  97.             int mx = *max_element(all(one));
  98.             int mn = *min_element(all(one));
  99.             if(mx - mn > k){
  100.                 return;
  101.             }
  102.             mx = *max_element(all(two));
  103.             mn = *min_element(all(two));
  104.             if(mx - mn > k){
  105.                 return;
  106.             }
  107.             maximize(ans, cnt);
  108.             return;
  109.         }
  110.         for(int i = 0; i <= 2; i++){
  111.             mask[pos] = i;
  112.             recursion(pos + 1);
  113.         }
  114.     }
  115.     void sol(void){
  116.         recursion(1);
  117.         cout<<ans<<endl;
  118.     }
  119. }
  120. namespace full{
  121.     void sol(void){
  122.         sort(a + 1,a + n + 1);
  123.         vector<int>left(n + 1);
  124.         vector<int>right(n + 1);
  125.         int lo = 1, hi = 2;
  126.         while(hi <= n){
  127.             while(lo <= hi && a[hi] - a[lo] > k){
  128.                 lo++;
  129.             }
  130.             left[hi] = (hi - lo + 1);
  131.             hi++;
  132.         }
  133.         int r = 1;
  134.         for(int l = 1; l <= n; l++){
  135.             while(r <= n && a[r] - a[l] <= k){
  136.                 r++;
  137.             }
  138.             right[l] = r - l;
  139.         }
  140.         vector<int>best_l(n + 1,0), best_r(n + 2,0);
  141.         for(int i = 1;i <= n; i++){
  142.             best_l[i] = max(best_l[i - 1], left[i]);
  143.         }
  144.         for(int i = n; i >= 1; i--){
  145.             best_r[i] = max(best_r[i + 1], right[i]);
  146.         }
  147.         int ans = 0;
  148.         for(int i = 1; i < n; i++){
  149.             maximize(ans, best_l[i] + best_r[i + 1]);
  150.         }
  151.         cout<<ans<<endl;
  152.     }
  153. }
  154. signed main(){
  155.     onii_chan;
  156.     baka; hentai;
  157.     if (fopen("stdin.txt", "r")) {
  158.         freopen("stdin.txt", "r", stdin);
  159.         freopen("stdout.txt", "w", stdout);
  160.     }
  161.     inp();
  162.     if(n <= 10)subtask_1::sol();
  163.     else full::sol();
  164.     return 0;
  165. }
  166.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/YmrTCJ
language:
C++14 (gcc 8.3)
created:
2 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!