UOJ Logo Universal Online Judge

UOJ

#187. 【UR #13】Ernd

统计

这里是跳蚤国中央广播电台,现在为您转播的是著名人类智慧大师 picks 博士与人工智能 betacome 之间的第二轮赛事。

这一场交锋的规则由网友 Po***QQ 提供,这位网友也将获得由不想跳的跳蚤不是好跳蚤——最强跳蚤跳跳跳公司提供的金牌跳蚤一只。

在刚刚结束的第一轮比赛中,因为 picks 博士在关键时刻出现了失误,他惜败给了 betacome。众所周知,A 先生在比赛前夕接受采访时,曾经说过相信 picks 博士可以以全胜的战绩战胜 betacome,请问 A 先生您现在怎么看?

“我仍然觉得 picks 博士的赢面要大一点,第一轮可能是因为他没有调整好心态,在比赛最后的水平堪比业余选手 m**o,这是非常反常的,如果他能够避免这样的失误的话,我觉得仍然觉得人类智慧可以取得最终的胜利。”

好,现在,我们可以看到,第二轮的比赛已经开始了,A 先生您能给我们简要介绍一下这一轮比赛的规则吗?

“好的,相信大家都玩过 osu 吧,这一场的规则来自 osu 的 ctb 模式。其实本来的规则是其他的模式,但是在 betacome 展示了它鬼畜的手速之后,经过比赛委员会的紧急讨论,决定把规则临时改成 ctb 模式。”

“简要来讲,你有一个盘子,时刻 $0$ 时你可以把盘子放到数轴上的任何一个整数坐标处,接着每一时刻你可以把盘子往左移动一个单位、往右移动一个单位或者不动。接着系统生成了 $n$ 个水果,第 $i$ 个水果会在第 $b_i$ 时刻出现在 $a_i$ 坐标处,保证 $b_i$ 单调递增。如果你的盘子在 $b_i$ 时刻恰好出现在 $a_i$ 处,那么就能接到这个水果。”

“最后一个水果落下后,游戏结束。分数用这个方式计算,定义变量 $K$,最开始 $K$ 是 $0$,按照顺序考虑每一个水果,如果你接到了当前水果,那么把 $K$ 加一,否则你的得分将加上 $K^2$ 并将 $K$ 清零,游戏结束后你的得分还会加上游戏结束时的 $K^2$。即你的得分是每一段连续接到水果的极长区间的长度平方和。”

好的,谢谢 A 先生,看来这场赛事的规则还是非常有趣的呀。现在我们节目组已经拿到了这场赛事中使用的水果信息(即数组 $a$ 与数组 $b$),A 先生您能帮我们计算双方可以拿到的最高分吗?

“当然,我们可以非常容易的算出来理论的最高分是****。” 出乎意料地,AcrossTheSky 居然一下子就说出了答案。

了解 AcrossTheSky 真实智力的你觉得这非常反常,你有理由怀疑 AcrossTheSky 是随便报了一个数字出来。所以你决定亲自计算一下答案,来检验一下 AcrossTheSky 是不是在瞎 BB。

输入格式

第一行一个正整数 $n$ ,表示水果的个数。

接下来 $n$ 行,第 $i$ 行包含两个空格分隔的正整数 $a_i,b_i$,表示第 $i$ 个水果会在第 $b_i$ 时刻出现在 $a_i$ 坐标处,保证 $b_i$ 单调递增

输出格式

输出一行一个正整数,表示这场赛事中双方可以拿到的最高分。

样例一

input

5
2 1
8 2
10 3
5 6
5 8

output

5

explanation

接住第 $1,4,5$ 或者第 $2,4,5$ 个水果,得分为 $1^2+2^2=5$ 。

容易证明这是得分最高的方案。

样例二

input

10
5 1
6 2
10 5
2 6
10 7
4 17
9 19
9 24
8 25
1 28

output

14

explanation

一种得到最高分的方案是,接住第 $1,2,5,7,8,9$ 个果子,总得分为 $2^2+1^2+3^2=14$ 。

样例三

见样例数据下载。这个数据中$n = 1000$ 。

限制与约定

由于一些原因,本题使用捆绑测试。每个子任务有若干个测试点,分为 $5$ 个子任务,你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

子任务 分值 限制
110$n\leq20$
210$n\leq1000$
320$n\leq10^5$,$a_i\leq5$
420$n\leq5\times10^5$,答案不超过$10^4$
540$n\leq5\times10^5$

对于所有数据,$1\leq n\leq5\times10^5$,$1\leq a_i,b_i\leq10^9$

时间限制:$2\texttt{s}$

空间限制:$128\texttt{MB}$

下载

样例数据下载