fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define Hoshimachi signed
  3. #define Suisei main
  4. using namespace std;
  5. #define int long long
  6. const int N=1e6+5;
  7. int n,k,a[N];
  8. bool used[N];
  9. void sub12(){
  10.     int total=0,saved=0;
  11.     for(int i=1; i<=n; i++){
  12.         total+=a[i];
  13.     }
  14.     sort(a+1,a+1+n);
  15.     for(int j=1; j<=n; j++){
  16.         for(int i=j-1; i>=1; i--){
  17.             if(!used[i] && a[j]-a[i]>=k){
  18.                 used[i]=1;
  19.                 saved+=a[i];
  20.                 break;
  21.             }
  22.         }
  23.     }
  24.     cout<<total-saved;
  25. }
  26. void sub3(){
  27.     sort(a+1,a+1+n,greater<int>());
  28.     int ans=0;
  29.     multiset<int> ms;
  30.     for(int i=1; i<=n; i++){
  31.         auto it=ms.lower_bound(a[i]+k);
  32.         if(it==ms.end()){
  33.             ans+=a[i];
  34.         }
  35.         else{
  36.             ms.erase(it);
  37.         }
  38.         ms.insert(a[i]);
  39.     }
  40.     cout<<ans; 
  41. }
  42. Hoshimachi Suisei(){
  43.     ios_base::sync_with_stdio(0);
  44.     cin.tie(0); cout.tie(0);
  45.     freopen("CHIAHANG.inp","r",stdin);
  46.     freopen("CHIAHANG.out","w",stdout);
  47.     cin>>n>>k;
  48.     for(int i=1; i<=n; i++){
  49.         cin>>a[i];
  50.     }
  51.     if(n<=1e4) sub12();
  52.     else sub3();
  53. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yMcGki
language:
C++14 (clang 8.0)
created:
5 hours 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!