fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class Main {
  5.     public static void main(String[] args) throws Exception {
  6.         FastScanner fs = new FastScanner(System.in);
  7.         int tests = fs.nextInt();
  8.         StringBuilder out = new StringBuilder();
  9.         while (tests-- > 0) {
  10.             int n = fs.nextInt();
  11.             long cap = fs.nextLong();
  12.             long[] arr = new long[n + 1];
  13.             long total = 0;
  14.             for (int i = 1; i <= n; i++) {
  15.                 arr[i] = fs.nextLong();
  16.                 total += arr[i];
  17.             }
  18.             if (n >= 3) Arrays.sort(arr, 2, n + 1);
  19.             int best = 0;
  20.             for (int pick = 1; pick <= n - 1; pick++) {
  21.                 long part = 0;
  22.                 int end = 2 + pick - 1;
  23.                 for (int j = 2; j <= end; j++) part += arr[j];
  24.                 long prod = (total - part) * part;
  25.                 part = 0;
  26.                 for (int j = n; j >= n - pick + 1; j--) part += arr[j];
  27.                 long prod2 = (total - part) * part;
  28.                 long use = Math.min(prod, prod2);
  29.                 if (use <= cap) best = pick;
  30.             }
  31.             out.append(n - best).append('\n');
  32.         }
  33.         System.out.print(out.toString());
  34.     }
  35.  
  36.     static final class FastScanner {
  37.         private final InputStream in;
  38.         private final byte[] buffer = new byte[1 << 16];
  39.         private int ptr = 0, len = 0;
  40.         FastScanner(InputStream is) { in = is; }
  41.         private int read() throws IOException {
  42.             if (ptr >= len) {
  43.                 len = in.read(buffer);
  44.                 ptr = 0;
  45.                 if (len <= 0) return -1;
  46.             }
  47.             return buffer[ptr++];
  48.         }
  49.         long nextLong() throws IOException {
  50.             int c;
  51.             while ((c = read()) <= 32) if (c == -1) return Long.MIN_VALUE;
  52.             int sign = 1;
  53.             if (c == '-') { sign = -1; c = read(); }
  54.             long val = 0;
  55.             while (c > 32) {
  56.                 val = val * 10 + (c - '0');
  57.                 c = read();
  58.             }
  59.             return val * sign;
  60.         }
  61.         int nextInt() throws IOException { return (int) nextLong(); }
  62.         String next() throws IOException {
  63.             int c;
  64.             while ((c = read()) <= 32) if (c == -1) return null;
  65.             StringBuilder sb = new StringBuilder();
  66.             while (c > 32) {
  67.                 sb.append((char)c);
  68.                 c = read();
  69.             }
  70.             return sb.toString();
  71.         }
  72.     }
  73. }
  74.  
Success #stdin #stdout 0.09s 54608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/G3hTCn
language:
Java (HotSpot 12)
created:
4 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!