fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ; 
  3.  
  4.  
  5. #define ll long long 
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define fir first 
  8. #define sec second 
  9. #define piint pair < int , int >
  10. #define FOR( i , a , b ) for (int i = (a) , _b = (b) ; i <= _b ; i ++ )  
  11. #define pb push_back 
  12. #define str string 
  13. #define ALL(a) (a).begin() , (a).end() 
  14. #define rep( i , a , b) for (int i = (a) ; i < (b) ; i ++ )
  15. #define ld long double
  16. const int maxn = 5 * 1e5;
  17. #define debug 0
  18. #define oo (ll)(1e18)
  19.  
  20.  
  21.  
  22. bool dp[maxn+3];
  23. ll a[maxn+3 ];
  24. ll sum[maxn+3];
  25.  
  26.  
  27. void input(){
  28. }
  29. #define name "TASK" 
  30. int main(){
  31.     fast 
  32.     if(fopen(name".INP","r")) {
  33.         freopen (name".INP","r",stdin);
  34.         freopen (name".OUT","w",stdout);
  35.     }
  36.     ll n ; cin >> n ;
  37.     ll k , d ;
  38.     cin >> k >> d ;
  39.  
  40.    	FOR ( i , 1 , n )  cin >> a[i];
  41.    	sort ( a + 1 , a + n + 1 );
  42.    	// voi moi cay but chi thuoc 1 hop 
  43.    	// va voi dieu kien la moi can trong day khong duoc chenh lech qua d 
  44.   	// neu no khong co con nao ai - aj <= d && aj - ai <= d thi phai tao them 1 hop but 
  45.   	// se co toi da n / k hop but 
  46.  
  47.  	FOR ( i , 0 , n ) dp[i] = 0 ;
  48.  	dp[0] = 1 ;
  49.  	sum[0] = 1 ;
  50.  
  51.  	int j = 1 ; 
  52.   	for (int i = 1 ; i <= n ; i ++ ) {
  53.   		while ( a[i] - a[j] > d && ( j + 1 ) <= i ) {
  54.   			j ++ ;
  55.   		}
  56.   		if ( i - j + 1 >= k ) {
  57.   			int c = sum[ i - k ] - ( (( j -1 ) > 0 )  ? sum[j-2] : 0) ; // sum[j-2];
  58.   			assert ( i >= k ) ;
  59.   			if ( c > 0 ) 
  60.   				dp[i] = 1 ;
  61.   		}
  62.   		sum[i] = sum[i-1] + dp[i] ;
  63.   	}
  64.   	if ( dp[n] ) cout << "YES" << '\n' ;
  65.   	else cout << "NO" << '\n' ;
  66.  
  67.  
  68.     cerr << "\nTIME: = " << (1.0*clock())/CLOCKS_PER_SEC << '\n';
  69.     return(0) ;
  70. }
Success #stdin #stdout #stderr 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
stderr
copy 
TIME: = 0.005962
https://ideone.com/9MM2cA
language:
C++14 (gcc 8.3)
created:
3 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!