TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4610
  • 题目
  • P4610【SDOI2016】征途
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,256m
    问题描述

    Pine 开始了从 S 地到 T 地的征途。

    从 S  地到 T  地的路可以划分成 n  段,相邻两段路的分界点设有休息站。
    Pine 计划用 m  天到达 T  地。除第 m  天外,每一天晚上 Pine 都必须在休息站过夜。所以,一段路必须在同一天中走完。
    Pine 希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。

    帮助 Pine 求出最小方差是多少。

    设方差是 v,可以证明,v×m^2​​ 是一个整数。为了避免精度误差,输出结果时输出 v×m^2。

    输入格式

    第一行两个数  n、m。
    第二行 n 个数,表示  n 段路的长度。

    输出格式

    一个数,最小方差乘以 m ^ 2 后的值。

    样例输入

    5 2
    1 2 5 8 6

    样例输出

    36

    提示

    对于 30%  的数据,1≤n≤10 ;
    对于 60% 的数据,1≤n≤100 ;
    对于 100%  的数据,1≤n≤3000 。

    保证从 S  到 T  的总路程不超过 30000。