fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static final long INF = (long)4e18;
  5.  
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  8.  
  9.         int T = sc.nextInt();
  10.  
  11.         while (T-- > 0) {
  12.  
  13.             int N = sc.nextInt();
  14.             long K = sc.nextLong();
  15.  
  16.             long[] X = new long[N];
  17.             long[] S = new long[N];
  18.  
  19.             for (int i = 0; i < N; i++)
  20.                 X[i] = sc.nextLong();
  21.  
  22.             for (int i = 0; i < N; i++)
  23.                 S[i] = sc.nextLong();
  24.  
  25.             long[] need = new long[N];
  26.             need[N - 1] = INF;
  27.  
  28.             for (int i = N - 2; i >= 0; i--) {
  29.  
  30.                 if (S[i] <= S[i + 1]) {
  31.                     need[i] = need[i + 1];
  32.                 } else {
  33.  
  34.                     long gap = X[i + 1] - X[i] - 1;
  35.                     long diff = S[i] - S[i + 1];
  36.  
  37.                     long t = (gap + diff - 1) / diff + 1;
  38.  
  39.                     need[i] = Math.min(t, need[i + 1]);
  40.                 }
  41.             }
  42.  
  43.             int ans = 0;
  44.  
  45.             for (int i = 0; i < N; i++)
  46.                 if (need[i] <= K)
  47.                     ans++;
  48.  
  49.             System.out.println(ans);
  50.         }
  51.     }
  52. }
Success #stdin #stdout 0.15s 56508KB
comments (?)
stdin
copy 
3
2 3
4 7
2 1
4 2
1 3 5 6
1 4 2 6
5 6
1 3 11 12 14
1 6 4 3 6
stdout
copy 
1
2
3
https://ideone.com/ZQ49y3
language:
Java (HotSpot 12)
created:
3 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!