蓝桥杯2024年第十五届决赛真题-最长子段

给定一个长度为 n 的序列 (s1, s2, · · · , sn) 和三个数 a, b, c ，你需要找出一对L, R 满足如下式子:

    ∑^R_i=Lsi > a(bR − cL), 1 ≤ L ≤ R ≤ n

    即，序列中的第 L 至 R 项之和大于 a · (b · R − c · L)，求出满足条件的 L, R中 R − L + 1 的最大值。

输入的第一行包含四个整数 n, a, b, c ，相邻整数之间使用一个空格分隔。

第二行包含 n 个整数 s1, s2, · · · , sn ，相邻整数之间使用一个空格分隔。

输出一行包含一个整数表示答案。

4 1 5 6
1 2 3 4

3

【评测用例规模与约定】

对于 60% 的评测用例，n ≤ 5000 ；

对于所有评测用例，1 ≤ n ≤ 3 × 10⁵ ，1 ≤ a, b, c ≤ 1000 ，|si| ≤ 10⁹ 。