#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define filein "euro.in"
#define fileout "euro.out"
#define maxn 34568
typedef struct { long li,ls,fs,fd,tata,lineindex; } nod;
double s[maxn],c[maxn],max[maxn],t;
long list[maxn];
nod arb[2*maxn];
long n,narb;
void readdata(void);
void buildtree(void);
void compute(void);
void writedata(void);
int main()
{
readdata();
buildtree();
compute();
writedata();
return 0;
}
void readdata(void)
{
long i;
double e;
freopen(euro.in,"r",stdin);
scanf("%ld %lf",&n,&t);
s[0]=0;
for (i=1;i<=n;i++)
{
scanf("%lf",&e);
s[i]=s[i-1]+e;
}
}
void buildtree(void)
{
long i,j,k,p;
for (i=1;i<=n;i++)
{
arb[i].li=arb[i].ls=list[i]=i;
arb[i].fs=arb[i].fd=arb[i].tata=0;
}
k=narb=n;
while (k>1)
{
j=0;
for (i=1;i<k;i++)
if (i%2==1)
{
narb++;
arb[narb].li=arb[list[i]].li;
arb[narb].ls=arb[list[i+1]].ls;
arb[narb].fs=list[i];
arb[narb].fd=list[i+1];
arb[list[i]].tata=narb;
arb[list[i+1]].tata=narb;
arb[narb].tata=0;
j++;
list[j]=narb;
}
if (k%2==1)
{
j++;
list[j]=list[k];
}
k=j;
}
}
double getmax(long i,long& lineindex)
{
long line,p;
double res;
line=-1;
p=i;
while (p>0)
{
if (arb[p].lineindex>line)
line=arb[p].lineindex;
p=arb[p].tata;
}
res=max[line]+c[line]*(i-line);
lineindex=line;
return res;
}
long locatelow(long line)
{
long poz,li,ls,m,lm;
double vline,vm;
li=line+1; ls=n; poz=n+1;
while (li<=ls)
{
m=(li+ls)>>1;
vline=max[line]+c[line]*(m-line);
vm=getmax(m,lm);
if (c[lm]<c[line])
{
if (vm<vline)
{
poz=m;
ls=m-1;
}
else
li=m+1;
}
else
ls=m-1;
}
return poz;
}
long locatehigh(long line)
{
long poz,li,ls,m,lm;
double vline,vm;
vm=getmax(n,lm);
vline=max[line]+c[line]*(n-line);
if (c[line]>c[lm] && vline>vm)
return n;
li=line+1; ls=n; poz=line;
while (li<=ls)
{
m=(li+ls)>>1;
vline=max[line]+c[line]*(long long)((m-line));
vm=getmax(m,lm);
if (c[lm]>c[line])
{
if (vm<vline)
{
poz=m;
li=m+1;
}
else
ls=m-1;
}
else
li=m+1;
}
return poz;
}
void setmax(long li,long ls,long num,long x)
{
long fs,fd;
fs=arb[num].fs;
fd=arb[num].fd;
if (li==arb[num].li && ls==arb[num].ls)
arb[num].lineindex=x;
else
if (li==arb[num].li)
{
if (arb[fd].li<=ls)
{
setmax(li,arb[fs].ls,fs,x);
setmax(arb[fd].li,ls,fd,x);
}
else
setmax(li,ls,fs,x);
}
else
if (ls==arb[num].ls)
{
if (arb[fs].ls>=li)
{
setmax(li,arb[fs].ls,fs,x);
setmax(arb[fd].li,ls,fd,x);
}
else
setmax(li,ls,fd,x);
}
else
{
if (ls<=arb[fs].ls)
setmax(li,ls,fs,x);
else
if (li>=arb[fd].li)
setmax(li,ls,fd,x);
else
{
setmax(li,arb[fs].ls,fs,x);
setmax(arb[fd].li,ls,fd,x);
}
}
}
void compute(void)
{
long i,j,p1,p2;
/* compute the C array */
for (i=0;i<=n;i++)
c[i]=s[n]-s[i];
/* init the tree */
for (i=1;i<=narb;i++)
arb[i].lineindex=0;
max[0]=0;
/* do the smart things */
for (i=1;i<n;i++)
{
max[i]=getmax(i,j)-t;
p1=locatelow(i);
p2=locatehigh(i);
if (p1<=p2)
{
setmax(p1,p2,narb,i);
}
}
}
void writedata(void)
{
long nouse;
freopen(fileout,"w",stdout);
printf("%.0lfn",getmax(n,nouse)-t);
}
Silaghi Raul Agent_Smith