Educational Codeforces Round 63 (Rated for Div. 2) D. Beautiful Array

http://codeforces.com/problemset/problem/1155/D

 表示取到位置  出现的和的最大值

 表示取到位置  前半部分的和 & 后半部分的和*k 的和的 最大值

 表示取到位置  并且中间有一段区间*k 的和的最大值

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[300005], dp[3][300005];
int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	ll ans = 0;
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
		dp[0][i] = max({ 0LL, dp[0][i - 1] + a[i] });
		dp[1][i] = max({ dp[1][i - 1] + a[i] * k,dp[0][i - 1] + a[i] * k,0LL });
		dp[2][i] = max({ dp[1][i - 1] + a[i],dp[2][i - 1] + a[i],0LL });
		ans = max({ ans,dp[0][i],dp[1][i],dp[2][i] });
	}
	printf("%lld\n", ans);
}