TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5411
  • 問題
  • P5411【继续欢乐】赚钱的游戏·第K大
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    問題説明

    \(n\) 堆石子排成一列,每堆石子数量可以是负数。

    一次游戏的过程是每次选择两堆相邻的石子,如果石子数量分别为 \(x,y\) 则合并时可以获得 \(xy\) 元人民币,将合并后的这堆石子放回原来的位置,一直操作直到只剩下一堆石子。玩游戏的人很机智,总是按照获得总人民币最多的方式进行游戏。

    如果选择范围 \(L,R\) 进行游戏,最多可以获得 \(f(l,r)\) 元,请计算出获得人民币前 \(k\) 多的范围,以及每个范围可以获得的人民币数量。如果两个范围获得的人民币一样多,优先输出 \(l\) 较小的范围;如果 \(l\) 也相等,优先输出 \(r\) 较小的。

    入力形式

    输入共两行。

    第一行两个整数 \(n,k\) ,表示石子的数量和需要计算前 \(k\) 大的方案。

    第二行 \(n\) 个整数,表示每堆石子的数量 \(a_1,a_2,\dots,a_n\)

    出力形式

    输出共 \(k\) 行。

    每行输出三个数 \(l,r,f(l,r)\),第 \(i\) 行表示第 \(i\) 大的方案。

    サンプル入力

    6 8
    2 1 2 1 -1 -1

    サンプル出力

    1 4 13
    1 3 8
    1 5 7
    2 4 5
    1 2 2
    1 6 2
    2 3 2
    3 4 2

    ヒント

    $1\leq n\leq 105, 1\leq k\leq \min \left\{105, \frac {n(n+1)}2\right\}, |a_i|\leq 500$


    ソース  感谢nodgd命题