Submission #959173


Source Code Expand

import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Supplier;

public class Main {
  void run() {
    int n = ni();
    int k = ni();
    int[] s = new int[n];
    for (int i = 0; i < n; ++i) {
      s[i] = ni();
      if (s[i] == 0) {
        System.out.println(n);
        return;
      }
    }
    int left = 0;
    int right = 0;
    long sum = 1;
    int max = 0;
    for (; ; ) {
      while (right < n && sum * s[right] <= k) {
        sum *= s[right];
        ++right;
        max = Math.max(max, right - left);
      }
      boolean flag = false;
      while (left < right && right < n && sum * s[right] > k) {
        sum /= s[left];
        ++left;
        flag = true;
      }
      if (right >= n) {
        break;
      }
      if (!flag && left == right) {
        ++left;
        ++right;
      }
    }
    System.out.println(max);
  }

  Scanner sc = new Scanner(System.in);

  public static void main(String[] args) {
    new Main().run();
  }

  int ni() {
    return Integer.parseInt(sc.next());
  }

  void debug(Object... os) {
    System.err.println(Arrays.deepToString(os));
  }

  class BIT<T> {
    int n;
    ArrayList<T> bit;
    BiFunction<T, T, T> bif;

    /**
     * 1-indexed なBinary Indexed Treeを構築する
     *
     * @param n   容量
     * @param bif 適用させる関数
     * @param sup 初期値
     */
    BIT(int n, BiFunction<T, T, T> bif, Supplier<T> sup) {
      this.n = n;
      bit = new ArrayList<>(n + 1);
      for (int i = 0; i < n + 1; ++i) {
        bit.add(sup.get());
      }
      this.bif = bif;
    }

    /**
     * iの位置の値をvで更新する
     *
     * @param i index
     * @param v 新しい値
     */
    void update(int i, T v) {
      for (int x = i; x <= n; x += x & -x) {
        bit.set(x, bif.apply(bit.get(x), v));
      }
    }

    /**
     * クエリー
     *
     * @param defaultValue 初期値
     * @param i            index
     * @return [1, i]までfを適用した結果
     */
    T reduce(T defaultValue, int i) {
      T ret = defaultValue;
      for (int x = i; x > 0; x -= x & -x) {
        ret = bif.apply(ret, bit.get(x));
      }
      return ret;
    }
  }

  long MOD = 1_000_000_007;

  /**
   * 繰り返し2乗法を用いたべき乗の実装
   *
   * @return a^r (mod 1,000,000,007)
   */
  long pow(long a, long r) {
    long sum = 1;
    while (r > 0) {
      if ((r & 1) == 1) {
        sum *= a;
        sum %= MOD;
      }
      a *= a;
      a %= MOD;
      r >>= 1;
    }
    return sum;
  }

  /**
   * 組み合わせ
   * O(n)
   *
   * @return {}_nC_r
   */
  long C(int n, int r) {
    long sum = 1;
    for (int i = n; 0 < i; --i) {
      sum *= i;
      sum %= MOD;
    }
    long s = 1;
    for (int i = r; 0 < i; --i) {
      s *= i;
      s %= MOD;
    }
    sum *= pow(s, MOD - 2);
    sum %= MOD;

    long t = 1;
    for (int i = n - r; 0 < i; --i) {
      t *= i;
      t %= MOD;
    }
    sum *= pow(t, MOD - 2);
    sum %= MOD;

    return sum;
  }

  double GOLDEN_RATIO = (1.0 + Math.sqrt(5)) / 2.0;

  /**
   * 黄金分割探索
   *
   * @param left  下限
   * @param right 上限
   * @param f     探索する関数
   * @param comp  上に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue)
   *              下に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue).reversed()
   * @return 極値の座標x
   */
  double goldenSectionSearch(double left, double right, Function<Double, Double> f, Comparator<Double> comp) {
    double c1 = divideInternally(left, right, 1, GOLDEN_RATIO);
    double c2 = divideInternally(left, right, GOLDEN_RATIO, 1);
    double d1 = f.apply(c1);
    double d2 = f.apply(c2);
    while (right - left > 1e-9) {
      if (comp.compare(d1, d2) > 0) {
        right = c2;
        c2 = c1;
        d2 = d1;
        c1 = divideInternally(left, right, 1, GOLDEN_RATIO);
        d1 = f.apply(c1);
      } else {
        left = c1;
        c1 = c2;
        d1 = d2;
        c2 = divideInternally(left, right, GOLDEN_RATIO, 1);
        d2 = f.apply(c2);
      }
    }
    return right;
  }

  /**
   * [a,b]をm:nに内分する点を返す
   */
  double divideInternally(double a, double b, double m, double n) {
    return (n * a + m * b) / (m + n);
  }

  long gcd(long a, long b) {
    if (b == 0) {
      return a;
    }
    return gcd(b, a % b);
  }

  int gcd(int a, int b) {
    if (b == 0) {
      return a;
    }
    return gcd(b, a % b);
  }

  long lcd(long a, long b) {
    return (a / gcd(a, b)) * b;
  }

  int lcd(int a, int b) {
    return (a / gcd(a, b)) * b;
  }

  /**
   * http://qiita.com/p_shiki37/items/65c18f88f4d24b2c528b
   */
  static class FastScanner {
    private final InputStream in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    public FastScanner(InputStream in) {
      this.in = in;
    }

    private boolean hasNextByte() {
      if (ptr < buflen) {
        return true;
      } else {
        ptr = 0;
        try {
          buflen = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (buflen <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    public boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    public long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }
  }
}

Submission Info

Submission Time
Task C - 列
User arukuka
Language Java8 (OpenJDK 1.8.0)
Score 100
Code Size 7024 Byte
Status AC
Exec Time 567 ms
Memory 47476 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 20 / 20 80 / 80
Status
AC × 4
AC × 27
AC × 44
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt
Subtask1 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_corner.txt, subtask1_killer1.txt, subtask1_killer2.txt, subtask1_killer3.txt, subtask1_killer4.txt, subtask1_killer5.txt
Subtask2 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_corner.txt, subtask1_killer1.txt, subtask1_killer2.txt, subtask1_killer3.txt, subtask1_killer4.txt, subtask1_killer5.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 265 ms 23576 KB
subtask0_sample_02.txt AC 261 ms 23520 KB
subtask0_sample_03.txt AC 263 ms 23620 KB
subtask0_sample_04.txt AC 264 ms 23604 KB
subtask1_01.txt AC 289 ms 24280 KB
subtask1_02.txt AC 287 ms 24080 KB
subtask1_03.txt AC 294 ms 24508 KB
subtask1_04.txt AC 286 ms 24104 KB
subtask1_05.txt AC 311 ms 25116 KB
subtask1_06.txt AC 295 ms 24628 KB
subtask1_07.txt AC 278 ms 24228 KB
subtask1_08.txt AC 309 ms 25524 KB
subtask1_09.txt AC 278 ms 24512 KB
subtask1_10.txt AC 293 ms 24180 KB
subtask1_11.txt AC 293 ms 24080 KB
subtask1_12.txt AC 292 ms 24880 KB
subtask1_13.txt AC 287 ms 24440 KB
subtask1_14.txt AC 295 ms 24748 KB
subtask1_15.txt AC 287 ms 24420 KB
subtask1_16.txt AC 290 ms 24536 KB
subtask1_17.txt AC 293 ms 24164 KB
subtask1_corner.txt AC 262 ms 23628 KB
subtask1_killer1.txt AC 262 ms 23648 KB
subtask1_killer2.txt AC 267 ms 23564 KB
subtask1_killer3.txt AC 262 ms 23616 KB
subtask1_killer4.txt AC 263 ms 23608 KB
subtask1_killer5.txt AC 267 ms 23612 KB
subtask2_01.txt AC 500 ms 45340 KB
subtask2_02.txt AC 515 ms 45600 KB
subtask2_03.txt AC 567 ms 45928 KB
subtask2_04.txt AC 530 ms 46160 KB
subtask2_05.txt AC 555 ms 45900 KB
subtask2_06.txt AC 559 ms 45284 KB
subtask2_07.txt AC 497 ms 45436 KB
subtask2_08.txt AC 509 ms 46480 KB
subtask2_09.txt AC 522 ms 46412 KB
subtask2_10.txt AC 535 ms 45924 KB
subtask2_11.txt AC 515 ms 46768 KB
subtask2_12.txt AC 543 ms 47476 KB
subtask2_13.txt AC 519 ms 45732 KB
subtask2_14.txt AC 547 ms 45688 KB
subtask2_15.txt AC 558 ms 46748 KB
subtask2_16.txt AC 522 ms 45816 KB
subtask2_17.txt AC 510 ms 45412 KB