#P4801. [CCO2015] 饥饿的狐狸

[CCO2015] 饥饿的狐狸

题目描述

本题译自 CCO 2015 Day1 T1「Hungry Fox

到你的宠物狐狸的晚餐时间啦!他的晚餐包含 NN 块饼干,第 ii 块饼干的温度是 TiT_i 摄氏度。同时,在晚餐中还包含了一大盘 WW 摄氏度的水。

在喝了一口水之后,你的狐狸开始吃饭了。每当他吃一块饼干时,这块饼干的美味度为当前饼干与吃/喝的前一样食物(包括饼干和水)的温度的差的绝对值。它可以在任意时间喝水(保证水喝不完),或按任意顺序吃饼干。

最后狐狸获得的美味值为它吃下的每块饼干的美味度之和。请求出狐狸获得的最小和最大的美味值。

输入格式

第一行两个整数 N,WN,W,表示饼干总数和水的温度。

接下来 NN 行,每行一个整数 Ti(1iN)T_i(1\le i\le N) 表示第 ii 块饼干的温度。

输出格式

输出两个整数,分别为狐狸获得的最小和最大的美味值。

3 20
18
25
18
7 16

提示

要得到最小美味值,一种可行的方案是,狐狸先喝水,然后吃第一块饼干,再吃第三块饼干,接着喝水,最后吃下第二块饼干,这样做,它所感受到的温度分别为 20,18,18,20,2520,18,18,20,25 摄氏度,总的美味度为 2+0+5=72+0+5=7

要得到最大美味值,一种可行的方案是,狐狸先喝水,然后按顺序吃饼干,它所感受到的温度分别为 20,18,25,1820,18,25,18 摄氏度,总的美味度为 2+7+7=162+7+7=16

对于 30%30\% 及以上的数据, W=0W=0

对于 100%100\% 的数据, $1\le N \le 100000, 0\le W \le 10^9, 0 \le T _ i \le 10 ^ 9$。