1155D - Beautiful Array - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
 
 
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
using namespace __gnu_pbds;
 

typedef tree<int, null_type,less_equal<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
    
    
typedef long double LD;
typedef long long ll;
#define pb push_back
#define pob pop_back
#define mp make_pair
#define rep(n) for (ll i = 0; i < n; i++)
#define FOR(i,a,b) for (i = a; i < b; i++)
#define repd(n) for (ll i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
#define back(v) v.rbegin(),v.rend()
#define wl(t) while(t --)
#define inrange(i,a,b) ((i>=min(a,b)) && (i<=max(a,b)))
#define isodd %2==1
#define iseven %2==0
typedef map<ll,ll> mii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> pii;
typedef vector<pii> vpii;
#define take(a,n) rep(n)cin>>a[i];
#define give(a,n) rep(n)cout<<a[i]<<' ';
 
#define FLSH fflush(stdout)
#define fileIO(name) \
    freopen(name".in", "r", stdin); \
    freopen(name".out", "w", stdout);
#define PRECISION(x) cout << fixed << setprecision(x); 
#define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
const ll MOD = 1000000007;
const ll FMOD = 998244353;
const double PI=3.1415926;
 
template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}
int add(int a, int b, int c = MOD){int res=a+b;return(res>=c?res-c:res);}
int mod_neg(int a, int b, int c = MOD){int res;if(abs(a-b)<c)res=a-b;else res=(a-b)%c;return(res<0?res+c:res);}
int mul(int a, int b, int c = MOD){ll res=(ll)a*b;return(res>=c?res%c:res);}
int muln(int a, int b, int c = MOD){ll res=(ll)a*b;return ((res%c)+c)%c;}
ll mulmod(ll a,ll b, ll m = MOD){ll q = (ll)(((LD)a*(LD)b)/(LD)m);ll r=a*b-q*m;if(r>m)r%=m;if(r<0)r+=m;return r;}
template<typename T>T expo(T e, T n){T x=1,p=e;while(n){if(n&1)x=x*p;p=p*p;n>>=1;}return x;}
template<typename T>T power(T e, T n, T m = MOD){T x=1,p=e;while(n){if(n&1)x=mul(x,p,m);p=mul(p,p,m);n>>=1;}return x;}
#define SORT(v) sort(all(v))
#define REVERSE(v) reverse(all(v))
#define sz(a) ll((a).size())
#define tr(container, it) for (decltype (container.begin()) it = container.begin(); it != container.end(); it++)
#define cpresent(container, element)(find(all(container), element) != container.end())
#define present(container, element)(container.find(element) != container.end())

ll fac[1000005];


ll power(ll x, ll y, ll p)
{
 
    // Initialize answer
    ll res = 1;
    x=x%p; 
    // Check till the number becomes zero
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if (y % 2 == 1)
            res = (res * x)%p;
 
        // y = y/2
        y = y >> 1;
 
        // Change x to x^2
        x = (x * x)%p;
    }
    return res % p;
}


ll modInverse(ll n,ll p)
{
    return power(n, p - 2, p);
}

ll nCr(ll n, ll r, ll p)
{
    // If n<r, then nCr should return 0
    if(r<0)return 0;
    if (n < r)
        return 0;
    // Base case
    if (r == 0)
        return 1;
    return (((fac[n] * modInverse(fac[r], p)) % p)
            * modInverse(fac[n - r], p)) % p;
}



// ll count(vector<ll> a, ll m, ll n)
// {
//     ll odd = 0, even = 0;
//     ll counter, i, j, p = 1;
//     ll pow_set_size = (1 << n);
// //  Given N prime numbers and a number M, find out how many numbers 
// //  from [1 to M] are divisible by any of the N given prime numbers. 
//     for (counter = 1; counter < pow_set_size; counter++) {
//         p = 1;
//         for (j = 0; j < n; j++) {
//             if (counter & (1 << j)) {
//                 p *= a[j];
//             }
//         }
//         if (__builtin_popcount(counter) & 1)odd += (m / p);
//         else even += (m / p);
//     }
 
//     return odd - even;
// }

// vi a,t1,t2;

// void build1(int v, int tl, int tr) {
//     if (tl == tr) {
//         t1[v] = a[tl];
//     } else {
//         int tm = (tl + tr) / 2;
//         build1(v*2, tl, tm);
//         build1( v*2+1, tm+1, tr);
//         t1[v] = max(t1[v*2] ,t1[v*2+1]);
//     }
// }


// ll q1(int v, int tl, int tr, int l, int r) {
//     if (l > r) 
//         return 0;
//     if (l == tl && r == tr) {
//         return t1[v];
//     }
//     int tm = (tl + tr) / 2;
//     return max(q1(v*2, tl, tm, l, min(r, tm)),q1(v*2+1, tm+1, tr, max(l, tm+1), r));
// }

// void update(int v, int tl, int tr, int pos, int new_val) {
//     if (tl == tr) {
//         t[v] = new_val;
//     } else {
//         int tm = (tl + tr) / 2;
//         if (pos <= tm)
//             update(v*2, tl, tm, pos, new_val);
//         else
//             update(v*2+1, tm+1, tr, pos, new_val);
//         t[v] = t[v*2] + t[v*2+1];
//     }
// }

// ll N=3167;
// ll N = 31627;
// ll N=1000005;
// vector<bool> isprime(N+5, true);
// vi pr;

// void seive(){
//     isprime[0] = isprime[1] = false;
//     for (ll i = 2; i <= N; i++) {
//         if (isprime[i]) {
//             for (ll j = i; j <= N; j += i){
//                 isprime[j] = false;
                
//             }
            
//         }
//     }
//     for (ll i = 2; i <= N; ++i)
//         if(isprime[i]) pr.pb(i);
// }

// vector<vi> adj;
// vi v;
// void dfs(ll i,ll p){
//     v.pb(i);
//     for(auto it:adj[i]){
//         if(it==p)continue;
//         dfs(it,i);
//         v[i]=max(v[i],v[it]+1);
        
//     }
// }


int main(void)
{
	FAST_IO;
	ll m,k,q,e,f,o,x,t,g,j,h,y,z,s,p,n,mn,mx,u,r,l;
	t=1;
	
	fac[0] = 1;
    for (ll i = 1; i < 1000005; i++)fac[i] = (fac[i - 1] * i) % FMOD;
    
    
    
    // seive();
    // cin>>t;
    while(t--){
        cin>>n>>x;
        ll a[n];
        take(a,n);
        ll dp[n+1][3][3];
        rep(n+1){
            FOR(j,0,3){
                FOR(k,0,3){
                    dp[i][j][k]=0;
                }
            }
        }
        rep(n){
            FOR(j,0,3){
                FOR(k,0,3){
                    if(j==2)dp[i+1][j][k]=max(dp[i][j][k],dp[i+1][j][k]);
                    if(k>0){
                        dp[i+1][j][k]=max(dp[i+1][j][k],dp[i+1][j][k-1]);
                    }
                    if(j>0){
                        dp[i+1][j][k]=max(dp[i+1][j][k],dp[i+1][j-1][k]);
                    }
                    p=1;
                    if(k==1)p=x;
                    if(j==1){
                        dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]+p*a[i]);
                    }
                }
            }
        }
        cout<<dp[n][2][2];

        // adj.resize(n);
        // rep(n)adj[i].clear();
        // v.clear();
        // v.resize(n,1);
        
        
    }
	   

	
    return 0;
}