题目详情题解（0）讨论（0）提交记录（0）

AT_arc128_c.[ARC128C] Max Dot

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定整数 NN、MM、SS，以及一个长度为 NN 的整数序列 A=(A1,A2,⋯ ,AN)A=(A_1,A_2,\cdots,A_N)。

请构造一个长度为 NN 的非负实数序列 x=(x1,x2,⋯ ,xN)x=(x_1,x_2,\cdots,x_N)，使其满足以下所有条件：

  • 0≤x1≤x2≤⋯≤xN≤M0 \leq x_1 \leq x_2 \leq \cdots \leq x_N \leq M
  • ∑1≤i≤Nxi=S\sum_{1 \leq i \leq N} x_i = S

定义 xx 的得分为 ∑1≤i≤NAi×xi\sum_{1 \leq i \leq N} A_i \times x_i。请你求出 xx 的得分可能取得的最大值。

输入格式

输入以如下格式从标准输入给出。

NN MM SS A1A_1 A2A_2 ⋯\cdots ANA_N

输出格式

请输出答案。如果你的答案的绝对误差或相对误差在 10−610^{-6} 以内，将被判定为正确。

输入输出样例

  • 输入#1

    3 2 3
1 2 3

    输出#1

    8.00000000000000000000

  • 输入#2

    3 3 2
5 1 1

    输出#2

    4.66666666666666666667

  • 输入#3

    10 234567 1000000
353239 53676 45485 617014 886590 423581 172670 928532 312338 981241

    输出#3

    676780145098.25000000000000000000

说明/提示

限制条件

  • 1≤N≤50001 \leq N \leq 5000
  • 1≤M≤1061 \leq M \leq 10^6
  • 1≤S≤min⁡(N×M,106)1 \leq S \leq \min(N \times M,10^6)
  • 1≤Ai≤1061 \leq A_i \leq 10^6
  • 输入的所有数值均为整数

样例解释 1

取 x=(0,1,2)x=(0,1,2) 是最优的。

样例解释 2

取 x=(2/3,2/3,2/3)x=(2/3,2/3,2/3) 是最优的。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页