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

#include <bits/stdc++.h>
#define ll long long
#define maxn 300005
using namespace std;
int n;
ll x, xx;
ll dp[maxn][3];

int main()
{
	scanf("%d%lld",&n,&x);
	ll ans = 0;
	for(int i=1;i<=n;i++) {
		scanf("%lld", &xx);
		dp[i][0] = max(0LL, dp[i-1][0] + xx);
		dp[i][1] = max(dp[i-1][0], dp[i-1][1]) + xx * x;
		dp[i][2] = max(dp[i-1][1], dp[i-1][2]) + xx;
		ans = max(dp[i][0], ans);
		ans = max(dp[i][1], ans);
		ans = max(dp[i][2], ans);
	}
	printf("%lld\n", ans);
	return 0;
}