题目描述
给定一个长度为 n 的正整数序列 a1,…,an 以及一个正整数 m 满足 m≥maxai。
你可以对序列进行任意次操作(也可以不操作)。每次操作你可以选择一个区间 [l,r],然后对于所有 l≤i≤r,令 ai←⌊aim⌋。
求可以得到的 ∑j=1naj 的最大值以及对应的最少操作次数。
输入格式
本题有多组测试数据。
第一行,一个正整数 T,表示测试数据组数。对于每组测试数据:
- 第一行,两个正整数 n,m。
- 第二行,n 个正整数 a1,…,an。
输出格式
对于每组测试数据,一行,两个非负整数,分别表示 ∑j=1naj 的最大值以及对应的最少操作次数。
3
2 5
1 2
5 10
1 5 2 4 3
10 10
1 4 2 5 1 6 2 7 1 10
7 1
28 3
80 5
提示
【样例解释】
对于样例的第二组测试数据:选择以下 3 组 [l,r] 即可得到最大值 28:
- [1,2];
- [2,5];
- [4,5]。
可以证明该方案是最优的之一。
【数据范围】
本题使用捆绑测试。
子任务编号 |
分值 |
n≤ |
∑n≤ |
特殊性质 |
1 |
9 |
4 |
400 |
无 |
2 |
27 |
103 |
104 |
3 |
11 |
105 |
106 |
A |
4 |
16 |
B |
5 |
37 |
无 |
- 特殊性质 A:ai≤m;
- 特殊性质 B:ai∣m。
对于所有数据:1≤T≤105,1≤n≤105,1≤∑n≤106,1≤ai≤m≤1012。