fork download
copy 
  1.  import java.io.*;
  2.     import java.util.*;
  3.  
  4.     class Solution{
  5.         InputStream is;
  6.         static PrintWriter out;
  7.         String INPUT = "";
  8.         static long mod = (long)1e9+7L;
  9.  
  10.         int n;
  11.         long k, b;
  12.         long[] a;
  13.         long[] memo;
  14.         public void solve(){
  15.             n=ni();              //taking input, n is size of input array.
  16.             k=nl(); b=nl();   
  17.             a=new long[n];
  18.             memo=new long[n];
  19.             Arrays.fill(memo, -1);
  20.             for(int i=0; i<n; i++)a[i]=nl();      //taking input of array
  21.             Arrays.sort(a);                  
  22.  
  23.             if(k == 0){                               //seprate case when k=0.
  24.                 int ct=0;
  25.                 for(int i=0; i<n; i++){
  26.                     if(a[i] >= b)ct+=1;
  27.                 }
  28.                 if(a[0] < b)ct+=1;
  29.                 out.println(ct);
  30.             }
  31.             else{                              //when k>0.
  32.                 out.println(f(n-1));
  33.             }
  34.  
  35.         }
  36.  
  37.         long f(int id){                            //top-down dp approach.
  38.             //out.println(id);
  39.             if(id<0)return 0;
  40.             if(memo[id] != -1){
  41.                 return memo[id];
  42.             }
  43.             if(id == 0){
  44.                 return memo[id] = 1;
  45.             }
  46.  
  47.             memo[id] = f(id-1);
  48.  
  49.             long nxt = (a[id]-b)/Math.max(1L, k);
  50.             int id1 = bs(0, id-1, nxt);                              //binary search for finding the index of nxt in the sorted array.
  51.             memo[id] = Math.max(memo[id], 1+f(id1));
  52.             return memo[id];
  53.         }
  54.  
  55.         int bs(int l, int r, long key){                    //binary search function.
  56.             while(l<r){
  57.                 int mid=l+(r-l+1)/2;
  58.                 if(a[mid] <= key)l=mid;
  59.                 else r=mid-1;
  60.             }
  61.             if(a[l] <= key){
  62.                 return l;
  63.             }
  64.             else{
  65.                 return -1;
  66.             }
  67.         }
  68.  
  69.  
  70.  
  71. 	//below is code for fast io.
  72.  
  73.         void run(){
  74.             is = new DataInputStream(System.in);
  75.             out = new PrintWriter(System.out);
  76.             int t=ni();while(t-->0)solve();
  77.             out.flush();
  78.         }
  79.         public static void main(String[] args)throws Exception{new Solution().run();}
  80.         long mod(long v, long m){if(v<0){long q=(Math.abs(v)+m-1L)/m;v=v+q*m;}return v%m;}
  81.         long mod(long v){if(v<0){long q=(Math.abs(v)+mod-1L)/mod;v=v+q*mod;}return v%mod;}
  82.         //Fast I/O code is copied from uwi code.
  83.         private byte[] inbuf = new byte[1024];
  84.         public int lenbuf = 0, ptrbuf = 0;
  85.         private int readByte(){
  86.             if(lenbuf == -1)throw new InputMismatchException();
  87.             if(ptrbuf >= lenbuf){
  88.                 ptrbuf = 0;
  89.                 try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
  90.                 if(lenbuf <= 0)return -1;
  91.             }
  92.             return inbuf[ptrbuf++];
  93.         }
  94.         private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
  95.         private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
  96.         private double nd() { return Double.parseDouble(ns()); }
  97.         private char nc() { return (char)skip(); }
  98.         private String ns(){
  99.             int b = skip();
  100.             StringBuilder sb = new StringBuilder();
  101.             while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
  102.                 sb.appendCodePoint(b);
  103.                 b = readByte();
  104.             }
  105.             return sb.toString();
  106.         }
  107.         private char[] ns(int n){
  108.             char[] buf = new char[n];
  109.             int b = skip(), p = 0;
  110.             while(p < n && !(isSpaceChar(b))){
  111.                 buf[p++] = (char)b;
  112.                 b = readByte();
  113.             }
  114.             return n == p ? buf : Arrays.copyOf(buf, p);
  115.         }
  116.         private char[][] nm(int n, int m){
  117.             char[][] map = new char[n][];
  118.             for(int i = 0;i < n;i++)map[i] = ns(m);
  119.             return map;
  120.         }
  121.         private int[] na(int n){
  122.             int[] a = new int[n];
  123.             for(int i = 0;i < n;i++)a[i] = ni();
  124.             return a;
  125.         }
  126.         private int ni(){
  127.             int num = 0, b;
  128.             boolean minus = false;
  129.             while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
  130.             if(b == '-'){
  131.                 minus = true;
  132.                 b = readByte();
  133.             }
  134.             while(true){
  135.                 if(b >= '0' && b <= '9'){
  136.                     num = num * 10 + (b - '0');
  137.                 }else{
  138.                     return minus ? -num : num;
  139.                 }
  140.                 b = readByte();
  141.             }
  142.         }
  143.         private long nl(){
  144.             long num = 0;
  145.             int b;
  146.             boolean minus = false;
  147.             while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
  148.             if(b == '-'){
  149.                 minus = true;
  150.                 b = readByte();
  151.             }        
  152.             while(true){
  153.                 if(b >= '0' && b <= '9'){
  154.                     num = num * 10 + (b - '0');
  155.                 }else{
  156.                     return minus ? -num : num;
  157.                 }
  158.                 b = readByte();
  159.             }
  160.         }
  161.         static  int i(long x){return (int)Math.round(x);}
  162.         static class Pair implements Comparable<Pair>{
  163.             long fs,sc;
  164.             Pair(long a,long b){
  165.                 fs=a;sc=b;
  166.             }
  167.             public int compareTo(Pair p){
  168.                 if(this.fs>p.fs)return 1;
  169.                 else if(this.fs<p.fs)return -1;
  170.                 else{
  171.                     return i(this.sc-p.sc);
  172.                 }
  173.                 //return i(this.sc-p.sc);
  174.             }
  175.             public String toString(){
  176.                 return "("+fs+","+sc+")";
  177.             }    
  178.         }
  179.  
  180.     } 
  181.  
  182.  
Success #stdin #stdout 0.1s 27984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DNbQbm
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

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!