33OJ
登录 注册
    传统题 文件IO:ring 1000ms 256MiB

环形赛场

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

M省要举办一场比赛,比赛地点是由 nn 个城市组成的环形城市群。这些城市按顺时针编号为 1,2,...,n1,2,...,n。每个城市都连接与它相邻的城市(与相邻的城市距离均为为 11),即城市 ii 与城市 i−1i - 1 和城市 i+1i + 1 可以相互到达(如果存在的话)。由于是环形,城市 11 与城市 nn 也可以相互到达。

城市 ii 的参赛人数为 aia_i 人,但是为了便于管理,只有至多 kk 个城市对外开放,参赛者只能从开放城市进入,然后通过相邻城市到达其参赛的城市。由于参赛者们长途跋涉已经很累了,每位参赛者移动 dd 距离会消耗 d2d^2 的体力。

参赛者们都很聪明,他们会自己选择距离目标城市最近的开放城市进入。

已知编号最小的开放城市为城市 xx,江桥想知道,通过合理地选择剩下的开放的城市,使得所有参赛者到达目标城市的总体力消耗最小是多少。

输入格式

从文件 ring.in 读入数据。 第一行输入三个正整数 n,k,xn,k,x。

第二行输入 nn 个正整数,表示 aia_i 。

输出格式

输出到文件 ring.out。 输出一个整数,代表答案。

6 2 2
2 5 4 2 6 2
10
6 2 1
4 2 5 6 3 2
12

解释

对于第 11 组数据,开放城市 22 和城市 55,城市 1,2,31,2,3 的参赛者从城市 22 进入,消耗的体力总和为 2+0+4=62 + 0 + 4 = 6,城市 4,5,64,5,6 的参赛者从城市 55 进入,消耗的体力总和为 2+0+2=42 + 0 + 2 = 4,因此总体力消耗为 1010,容易证明这就是最优解。

样例 3

见 ring3.in 与 ring3.ans。

样例 4

见 ring4.in 与 ring4.ans。

样例 5

见 ring5.in 与 ring5.ans。

样例 6

见 ring6.in 与 ring6.ans。

样例 7

见 ring7.in 与 ring7.ans。

数据规模与约定

下发文件分别对应子任务 1,2,3,4,51,2,3,4,5。

有合理的子任务依赖。

子任务编号 n≤n≤ 特殊性质 分值
11 1010 55
22 2×1032 \times 10^3 k=1k = 1 1515
33 10210^2 2020
44 2×1032 \times 10^3 k≤2k \le 2 2525
55 3535

对于 100%100\% 的数据:保证 $1 \leq n \leq 2 \times 10^3, 1 \leq k \leq min(n,10),1 \leq a_i \leq 10^6$。

时空限制:11 秒 / 256 MiB256\,\mathrm{MiB}。

【评测&补题】三三信奥国庆模拟赛第六场

未参加
状态
已结束
规则
IOI
题目
6
开始于
2026-10-7 12:00
结束于
2026-10-28 8:00
持续时间
500 小时
主持人
参赛人数
56