1787C - Remove the Bracket - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
#define ls p<<1
#define rs p<<1|1
#define Ma 1000005
#define mod 1000000007
#define PLL pair<ll,ll>
#define PDD pair<double,double>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define N 61
#define pb push_back
#define ld long double
#define inf 1e18
using namespace std;
ll n,s;
ll a[Ma];
ll x[Ma],y[Ma];
ll dp[Ma][2];

void sol()
{
	scanf("%lld%lld",&n,&s);
	for (ll i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for (ll i=2;i<n;i++)
	{
		x[i]=min(s,a[i]),y[i]=a[i]-x[i];
		if (x[i]>y[i])
			swap(x[i],y[i]);
	}
	dp[2][0]=x[2]*a[1],dp[2][1]=y[2]*a[1];
	for (ll i=3;i<n;i++)
	{
		dp[i][0]=min(dp[i-1][0]+y[i-1]*x[i],dp[i-1][1]+x[i-1]*x[i]);
		dp[i][1]=min(dp[i-1][0]+y[i-1]*y[i],dp[i-1][1]+x[i-1]*y[i]);
	}	
	printf("%lld\n",min(dp[n-1][0]+y[n-1]*a[n],dp[n-1][1]+x[n-1]*a[n]));
	return;
}

int main()
{
	ll tt;
	scanf("%lld",&tt);
	while (tt--)
		sol();
	return 0;
}