UOJ Logo

NOI.AC

#61. sequence

统计

sequence

题目描述

给一个序列 $A$ ,你可以进行 $k$ 次交换操作,最大化最大子段和。

输入格式

第一行两个整数 $n, k$ 。

第二行一共 $n$ 个数,表示序列 $A$ 。

输出格式

第一行两个数,表示最大字段和的最大值,以及你进行的交换次数 $p$ 。要求 $p \leq k$ 。

接下来 $p$ 行每行两个数,表示交换的下标。

最后一行两个数,表示和最大的子段的左右端点。

样例

输入

3 3
1 -2 3

输出

4 2
1 2
2 3
2 3

数据范围

$n \leq 10^5, k \leq 10, |A_i| \leq 10^9$ 。

Subtask1 ($20\%$) : $n \leq 10$ 。

Subtask2 ($30\%$) : $n \leq 1000$ 。

Subtask3 ($20\%$) : $k = 1$ 。

Subtask4 ($30\%$) :无特殊性质。

时间限制:$1s$ 。

空间限制: $256MB$ 。