Educational Codeforces Round 63 D. Beautiful Array

时间:2022-02-05 08:46:46
D. Beautiful Array
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array aa consisting of nn integers. Beauty of array is the maximum sum of some consecutive subarray of this array (this subarray may be empty). For example, the beauty of the array [10, -5, 10, -4, 1] is 15, and the beauty of the array [-3, -5, -1] is 0.

You may choose at most one consecutive subarray of aa and multiply all values contained in this subarray by xx. You want to maximize the beauty of array after applying at most one such operation.

Input

The first line contains two integers nn and xx (1≤n≤3⋅105,−100≤x≤100) — the length of array aa and the integer xx respectively.

The second line contains nn integers a1,a2,…,an (−109≤ai≤109) — the array aa.

Output

Print one integer — the maximum possible beauty of array aa after multiplying all values belonging to some consecutive subarray x.

Examples
input
5 -2
-3 8 -2 1 -6
output
22
input
12 -3
1 3 3 7 1 3 3 7 1 3 3 7
output
42
input
5 10
-1 -2 -3 -4 -5
output
0
Note

In the first test case we need to multiply the subarray [-2, 1, -6], and the array becomes [-3, 8, 4, -2, 12] with beauty 22([-3, 8, 4, -2, 12]).

In the second test case we don't need to multiply any subarray at all.

In the third test case no matter which subarray we multiply, the beauty of array will be equal to 0.

果然还是太菜了,简单dp都想不出来。

dp[0] 记录不使用x的最大值

dp[1] 记录允许使用x的情况下的最大值

dp[2]记录在前面的区间中已经使用了x的情况下的最大值(尽管可能使用x的区间对最大值并没有贡献)

#include<cstdio>
#include<algorithm>
using namespace std; long long arr[]; int main(){
int n, x;
long long dp[] = {},ans=;
scanf("%d%d",&n,&x);
for(int i=;i<n;i++){
scanf("%I64d",&arr[i]);
dp[] = max(0ll,dp[]+arr[i]);
dp[] = max(dp[],dp[]+arr[i]*x);
dp[] = max(dp[],dp[]+arr[i]);
ans = max(ans,dp[]); }
printf("%I64d\n",ans);
return ; }

Educational Codeforces Round 63 D. Beautiful Array的更多相关文章

  1. &lbrack;Educational Codeforces Round 63 &rsqb; D&period; Beautiful Array (思维&plus;DP)

    Educational Codeforces Round 63 (Rated for Div. 2) D. Beautiful Array time limit per test 2 seconds ...

  2. Educational Codeforces Round 63 &lpar;Rated for Div&period; 2&rpar; 题解

    Educational Codeforces Round 63 (Rated for Div. 2)题解 题目链接 A. Reverse a Substring 给出一个字符串,现在可以对这个字符串进 ...

  3. Educational Codeforces Round 63部分题解

    Educational Codeforces Round 63 A 题目大意就不写了. 挺简单的,若果字符本来就单调不降,那么就不需要修改 否则找到第一次下降的位置和前面的换就好了. #include ...

  4. Educational Codeforces Round 63 选做

    D. Beautiful Array 题意 给你一个长度为 \(n\) 的序列.你可以选择至多一个子段,将该子段所有数乘上给定常数 \(x\) .求操作后最大的最大子段和. 题解 考虑最大子段和的子段 ...

  5. Educational Codeforces Round 63 &lpar;Rated for Div&period; 2&rpar; D&period; Beautiful Array &lpar;简单DP&rpar;

    题目:https://codeforces.com/contest/1155/problem/D 题意:给你n,x,一个n个数的序列,你可以选择一段区间,区间的数都乘以x,然后求出最大字段和 思路: ...

  6. Educational Codeforces Round 63 &lpar;Rated for Div&period; 2&rpar; D&period; Beautiful Array 分类讨论连续递推dp

    题意:给出一个 数列 和一个x 可以对数列一个连续的部分 每个数乘以x  问该序列可以达到的最大连续序列和是多少 思路: 不是所有区间题目都是线段树!!!!!! 这题其实是一个很简单的dp 使用的是分 ...

  7. Educational Codeforces Round 63 &lpar;Rated for Div&period; 2&rpar; D&period; Beautiful Array(动态规划&period;递推)

    传送门 题意: 给你一个包含 n 个元素的序列 a[]: 定义序列 a[] 的 beauty 为序列 a[] 的连续区间的加和最大值,如果全为负数,则 beauty = 0: 例如: a[] = {1 ...

  8. Educational Codeforces Round 12 E&period; Beautiful Subarrays 字典树

    E. Beautiful Subarrays 题目连接: http://www.codeforces.com/contest/665/problem/E Description One day, ZS ...

  9. Educational Codeforces Round 11 A&period; Co-prime Array 水题

    A. Co-prime Array 题目连接: http://www.codeforces.com/contest/660/problem/A Description You are given an ...

随机推荐

  1. 搜狗输入法wp风格皮肤

    换了个nexus 发现输入法真的没有wp的好用 没办法,刚好搜狗输入法有定制皮肤的选项,所以自己做了个wp风格的输入法皮肤. 一点微小的工作 http://pan.baidu.com/s/1kVsHd ...

  2. Cordova for iOS&lbrack; PhoneGap&rsqb;

    安装这个费了点劲,和早前的PhoneGap有些不同. Cordova支持如下移动操作系统:iOS, Android,ubuntu phone os, Blackberry, Windows Phone ...

  3. 迅为iTOP-4412开发板Ubuntu操作系统烧写方法

    本文转自:http://www.topeetboard.com Ubuntu系统烧写硬件平台:iTOP4412开发板 需要准备:串口线.读卡器.一张SD卡最好是2G(自备).另外一张卡(大于等于2G都 ...

  4. CreateObject&lpar;&quot&semi;Wscript&period;Shell&quot&semi;&rpar;用法

    WScript.Shell是WshShell对象的ProgID,创建WshShell对象可以运行程序.操作注册表.创建快捷方式.访问系统文件夹.管理环境变量. 该对象有一个run方法. Run 方法创 ...

  5. SAS软件的使用和统计学分析的初步介绍

           一般而言我们都会使用Excel来统计测试结果,除了Excel之外,还有SAS等软件,也是可以统计测试结果的,本人也是SAS的初学者,现在我就给大家介绍一下SAS的简单使用,随着我不断的学 ...

  6. 在C语言中以编程的方式获取函数名

    仅仅为了获取函数名,就在函数体中嵌入硬编码的字符串,这种方法单调乏味还易导致错误,不如看一下怎样使用新的C99特性,在程序运行时获取函数名吧. 对象反射库.调试工具及代码分析器,经常会需要在运行时访问 ...

  7. angular4——安装

    本文同样适用于NG4,最近开始学ng2了,前端小白一枚啊,做过安卓开发,做过java写的服务器啊,热爱前端啊,所以就开坑了,入坑之前建议先学下es6哦,学完后看下typescript哦,正所谓,前面基 ...

  8. IntelliJ IDEA运行项目成功后,无法访问Tomcat主页

    问题 初次使用IntelliJ IDEA,但今天在运行项目启动Tomcat后,发现无法访问Tomcat首页,出现404错误:输入http://localhost:8080时无法访问Tomcat首页,但 ...

  9. SEED实验——Environment Variable and Set-UID Program实验报告

    任务一:操作环境变量 实验过程一: 用printenv或env打印出环境变量. 在终端输入命令,显示结果如下图所示: 经过实验发现,printenv和env均可输出当前系统的环境变量.不同的是prin ...

  10. Book : &lt&semi;Hands-on ML with Sklearn &amp&semi; TF&gt&semi; pdf&sol;epub

    非常好的书,最近发现了pdf版本,链接:http://www.finelybook.com/hands-on-machine-learning-with-scikit-learn-and-tensor ...