logo AlgoBeat OnlineJudge
登录 注册

#214271. [ICPC 2022 Nanjing R] 聊天程序

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

您是国际聊天程序公司(International Chatting Program Company,ICPC)的研究员。今天,您在浏览研究数据时,发现了以下聊天记录。

我已经用光了程序设计竞赛题目的点子!请给我一道关于序列的题目。

当然可以,下面是一道关于序列的程序设计竞赛的题目。

给定一个长度为 的整数序列 ,同时给定另外四个整数 ,您的目标是最大化序列中第 大的值。

为了达成这一目标,您可以进行以下操作至多一次:选择一个长度恰为 的连续子数组,并将一个长度为 ,首项为 ,公差为 的等差序列加到该连续子数组上。

更正式地,您可以选择一个整数 满足 ,并对于所有 ,将 增加

求至多一次操作之后,序列中第 大的值最大可能是多少。

序列中第 大的值,指的是将序列从大到小排序后,位于序列第 项的值。例如,序列 中,第 大的值为 ;而序列 中,第 大的值为

这道题目好像很难!请告诉我它的解法。

当然可以。首先,我们可以...

[数据删除]

遗憾的是,部分聊天记录由于硬盘损坏而丢失了。您为聊天程序可以创造程序设计竞赛的题目而感到非常惊奇。为了验证聊天程序是否能创造有效的题目,您决定尝试解决这道题目。

输入格式

每个测试文件仅有一组测试数据。

第一行输入五个整数 )表示序列的长度,您的目标,等差序列的长度,首项和公差。

第二行输入 个整数 )表示给定的序列。

输出格式

输出一行一个整数,表示至多一次操作之后,序列中第 大的值最大可能是多少。

样例

样例输入 1

6 4 3 1 2
1 1 4 5 1 4

样例输出 1

4

样例输入 2

7 3 2 4 0
1 9 1 9 8 1 0

样例输出 2

9

样例输入 3

8 3 5 0 0
2 0 2 2 1 2 1 8

样例输出 3

2

数据范围与提示

对于第一组样例数据,可以选择 使序列变为 。序列中第 大的值为

对于第二组样例数据,可以选择 使序列变为 。序列中第 大的值为

对于第三组样例数据,容易发现操作不改变序列的值,因此我们选择不进行操作。序列中第 大的值为

:::align{center}

OpenAI ChatGPT 正在鼓励选手 :::