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

AT_abc240_f.[ABC240F] Sum Sum Max

提高+/省选-

通过率：0%

AC君温馨提醒

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

题目描述

有三个数列 A,B,CA,B,C。

其中 CC 表示为 $ x_1,\ \dots,\ x_N,\ y_1,\ \dots,\ y_N $ 的形式，意思是前 y1y_1 个数为 x1x_1,之后 y2y_2 个数为 x2x_2……最后 yNy_N 个数为 xNx_N。

BB 为 CC 的前缀和数组。

AA 为 BB 的前缀和数组。

求 AA 中最大值。

输入格式

对于每组数据，

第一行为两个数 NN 和 MM，

第 22 至 N+1N+1 行，第 ii 行为两个数 xi−1x_{i-1} 和 yi−1y_{i-1}。

输出格式

对于每组数据，输出一行一个整数表示答案

样例 #1

样例输入 #1

3
3 7
-1 2
2 3
-3 2
10 472
-4 12
1 29
2 77
-1 86
0 51
3 81
3 17
-2 31
-4 65
4 23
1 1000000000
4 1000000000

样例输出 #1

4
53910
2000000002000000000

输入输出样例

  • 输入#1

    3
3 7
-1 2
2 3
-3 2
10 472
-4 12
1 29
2 77
-1 86
0 51
3 81
3 17
-2 31
-4 65
4 23
1 1000000000
4 1000000000

    输出#1

    4
53910
2000000002000000000

说明/提示

  • $ 1\ \leq\ T\ \leq\ 2\ \times\ 10^5 $
  • $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $
  • $ \sum\ N\ \leq\ 2\times\ 10^5 $
  • $ 1\ \leq\ M\ \leq\ 10^9 $
  • $ |x_i|\ \leq\ 4\ ,\ (1\ \leq\ i\ \leq\ N) $
  • $ y_i\ \gt\ 0\ ,\ (1\ \leq\ i\ \leq\ N) $
  • $ \sum_{k\ =\ 1}^N\ y_k\ =\ M $

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

首页