题目详情题解（0）讨论（0）提交记录（0）

AT_arc169_b.[ARC169B] Subsegments with Small Sums

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个正整数 SS。对于正整数序列 xx ，我们定义函数 f(x)f(x) 如下:

  • 将 xx 分解为几个连续的子序列。对于每个连续子序列，其元素之和最多为 SS。f(x)f(x) 是在这样的要求下分解成的连续子序列的最小数目。

现在给定一个长度为 NN 的正整数序列 A=(A1,A2,⋯ ,AN)A=(A_1,A_2,\cdots,A_N)，请求出 ∑1≤l≤r≤Nf((Al,Al+1,⋯ ,Ar))\sum_{1 \leq l \leq r \leq N} f((A_l,A_{l+1},\cdots,A_r))。

输入格式

第一行两个整数 NN 和 SS。

第二行 NN 个整数表示序列 AA。

输出格式

一行一个整数 ∑1≤l≤r≤Nf((Al,Al+1,⋯ ,Ar))\sum_{1 \leq l \leq r \leq N} f((A_l,A_{l+1},\cdots,A_r))。

输入输出样例

  • 输入#1

    3 3
1 2 3

    输出#1

    8

  • 输入#2

    5 1
1 1 1 1 1

    输出#2

    35

  • 输入#3

    5 15
5 4 3 2 1

    输出#3

    15

  • 输入#4

    20 1625597454
786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130

    输出#4

    588

说明/提示

1≤N≤2500001 \leq N \leq 250000，1≤S≤10151 \leq S \leq 10^{15}，1≤Ai≤min⁡(S,109)1 \leq A_i \leq \min(S,10^9)，所有输入都是整数。

样例一解释：

样例中 x=(1,2,3)x=(1,2,3)。分解方案 (1,2),(3)(1,2),(3) 满足条件，可以证明没有分解成少于两个连续子序列的方案满足条件，所以 f((1,2,3))=2f((1,2,3))=2。

下面显示的是可能的 l,rl,r 和对应的 ff 值:

  • (l,r)=(1,1)(l,r)=(1,1)：f((1))=1f((1))=1
  • (l,r)=(1,2)(l,r)=(1,2)：f((1,2))=1f((1,2))=1
  • (l,r)=(1,3)(l,r)=(1,3)：f((1,2,3))=2f((1,2,3))=2
  • (l,r)=(2,2)(l,r)=(2,2)：f((2))=1f((2))=1
  • (l,r)=(2,3)(l,r)=(2,3)：f((2,3))=2f((2,3))=2
  • (l,r)=(3,3)(l,r)=(3,3)：f((3))=1f((3))=1

因此，答案是1+1+2+1+2+1=81+1+2+1+2+1=8。

输入解题思路，AI测评打分。不知道怎么写?

首页