P7291 「EZEC-5」人赢 加强版

题目背景

> “我们在 小 Z 面前秀个恩爱吧。”\ >“好的。” 小 Z 发现他身边都是人赢,这使他非常自闭。 小 Z 又看着身边的潇,不禁陷入了沉思…… ![](https://cdn.luogu.com.cn/upload/image_hosting/b1ij58kc.png)

题目描述

潇有一个数组 $k$,下标为 $1$ 到 $n$ 。 潇定义 $f(x,y)=\begin{cases} \min(k_x,k_y) \times (x + y) &x \ne y \\ k_x\times x&x=y \end{cases}$ 。 潇想知道对于任意的 $1 \le x,y \le n$,$f(x,y)$ 的最大值是多少。但是她不会做,于是就问了善良的 小 Z,然而非常想在妹子面前表现的 小 Z 发现他也不会做,就只能够求助善良的你了。

输入格式

输出格式

说明/提示

### 数据范围 **本题采用捆绑测试。** - Subtask 1(10 points):$1 \le n \le 50$。 - Subtask 2(20 points):$1 \le n \le 5000$。 - Subtask 3(20 points):$1 \le n \le 10^6$。 - Subtask 4(10 points):保证所有 $k_{i}$ 都相等。 - Subtask 5(40 points):无特殊限制。 对于 $100\%$ 的数据,$1 \le n \le 10^7$,$1 \le k_{i} \le 10^9$。 **本题建议使用较快的读入方式。** std 使用的快读: ```cpp #define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1