[Educational Codeforces Round 63 ] D. Beautiful Array （思维+DP）

Educational Codeforces Round 63 (Rated for Div. 2)

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≤1001≤n≤3⋅105,−100≤x≤100) — the length of array aa and the integer xx respectively.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (−109≤ai≤109−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 xx.

Examples

input

Copy

5 -2
-3 8 -2 1 -6

output

Copy

input

Copy

12 -3
1 3 3 7 1 3 3 7 1 3 3 7

output

Copy

input

Copy

5 10
-1 -2 -3 -4 -5

output

Copy

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.

题意：

给你一个含有n个数字的数组，和一个整数x

你可以选择一个连续的区间\([l,r]\) 然后\(a[l]\)到\(a[r]\) 每一个数\(a[i]\) 变为\(a[i]*x\)

使改变后的数组的最大连续子段和最大。

思路：

动态规划解决该问题：

设\(dp[i][0]\) 代表到第i个位置，没乘以x的最大子段和。

设\(dp[i][1]\) 代表到第i个位置，结尾是乘以x的最大子段和。

设\(dp[i][2]\) 代表到第i个位置，前面有乘以x的，但是当前结尾是没乘x的最大子段和。

转移方程：

dp[i][0] = max(0ll, dp[i - 1][0]) + a[i];
        dp[i][1] = max(max(dp[i - 1][1], dp[i - 1][0]), 0ll) + x * a[i];
        dp[i][2] = max(max(dp[i - 1][2], dp[i - 1][1]), 0ll) +  a[i];
        ans = max(ans, max(dp[i][0], max(dp[i][1], dp[i][2])));

AC 代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}

inline void getInt(int *p);
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n;
ll x;
ll a[maxn];
ll dp[maxn][4];
int main()
{
    //freopen("D:\\code\\text\\input.txt","r",stdin);
    //freopen("D:\\code\\text\\output.txt","w",stdout);
    gbtb;
    cin >> n >> x;
    ll sum = 0ll;
    repd(i, 1, n) {
        cin >> a[i];
        sum += a[i];
    }
    ll ans = 0ll;
    ans = max(ans, sum);
    repd(i, 1, n) {
        dp[i][0] = max(0ll, dp[i - 1][0]) + a[i];
        dp[i][1] = max(max(dp[i - 1][1], dp[i - 1][0]), 0ll) + x * a[i];
        dp[i][2] = max(max(dp[i - 1][2], dp[i - 1][1]), 0ll) +  a[i];
        ans = max(ans, max(dp[i][0], max(dp[i][1], dp[i][2])));
    }
    cout << ans << endl;
    return 0;
}

inline void getInt(int *p)
{
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    } else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}