#include <stdio.h>
#define filein "euro.in"
#define fileout "euro.out"
#define MAXN 34567
int t;
struct val {
int val, pos, back;
long long max;
} e[MAXN];
int ne;
void read_in(void)
{
int i, n, a[MAXN];
freopen(filein, "r", stdin);
scanf("%d%d", &n, &t);
for(i = 0; i < n; i++)
scanf("%d", a + i);
for(i = 0; i < n - 1; i++) {
e[ne].val += a[i];
if(e[ne].val < 0)
e[ne++].pos = i + 1;
}
e[ne].val += a[n - 1];
e[ne++].pos = n;
}
int main()
{
int i, j, totsum, parsum, back;
long long max;
read_in();
totsum = e->val;
e->back = 0;
e->max = (long long) totsum * e->pos - t;
for(i = 1; i < ne; i++) {
totsum += e[i].val;
max = (long long) totsum * e[i].pos;
back = 0;
parsum = e[i].val;
for(j = i - 1; (j >= e[i - 1].back) && (i - j <= 200); j--) {
if((long long) parsum * e[i].pos + e[j].max > max) {
max = (long long) parsum * e[i].pos + e[j].max;
back = j;
}
parsum += e[j].val;
}
e[i].back = back;
e[i].max = max - t;
}
freopen(fileout,"w",stdout);
printf("%Ldn", e[ne - 1].max);
return(0);
}
(2) -> O(N*(logN)2)
#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(euro.out,"w",stdout);
printf("%.0lfn",getmax(n,nouse)-t);
}
Silaghi Raul Agent_Smith