> #include <iostream>
> #include <cstdio>
> #include <algorithm>
> #include <cstring>
> #define maxn 100100
> using namespace std;
> typedef long long ll;
> ll l,r,a[maxn]={0},t[maxn]={0};
> 
> typedef struct
> {
> 	ll res;
> 	ll l;
> 	ll r;
> } cao;
> cao ans;
> ll sum[maxn]={0};
> cao fenzi(ll left,ll right)
> {
>   if(right-left==1)
>   {
>   	cao gan={a[left]*a[left],left,left};
>   	return gan;
>   }
>   ll m=(left+right)/2;
>   cao maxl=fenzi(left,m);
>   cao maxr=fenzi(m,right);
>   cao maxf;
>   if(maxl.res>maxr.res)
> 	memcpy(&maxf,&maxl,sizeof(cao));
>   else
> 	memcpy(&maxf,&maxr,sizeof(cao));
>   ll v=0,s=0;
>   ll p=m-1,q=m,l=m-1,r=m;
>   v=a[l]+a[r];
>   s=v*(a[l]<a[r]?a[l]:a[r]);
>   for(ll i=1;p-i>=left||q+i<right;i++)
>   {
>     if(p-i>=left)
> 	{
> 	  v=sum[r]-sum[p-i-1];
> 	  sort(t+p-i,t+r+1);
> 	  if(v*t[p-i]>s)
> 	  {
> 	  	s=v*t[p-i];
>         l=p-i;
> 	  }
> 	  memcpy(t+p-i,a+p-i,sizeof(ll)*(r-p+i+1));
> 	}
>     if(q+i<right)
> 	{
> 	  v=sum[q+i]-sum[l-1];
> 	  sort(t+l,t+q+i+1);
>       if(v*t[l]>s)
> 	  {
> 	  	r=q+i;
> 	  	s=v*t[l];
> 	  }
> 	  memcpy(t+l,a+l,sizeof(ll)*(q+i-l+1));
> 	}
>   }
>   cao nimei={s,l,r};
>   if(nimei.res>maxf.res)
> 	return nimei ;
>   else
> 	return maxf;
> }
> int main()
> {
>     ll n;
>    while( scanf("%lld",&n)!=EOF)
> {
> 
>     for(int i=1;i<=n;i++)
> 	scanf("%lld",a+i),sum[i]=a[i]+sum[i-1];
>     memcpy(t+1,a+1,sizeof(ll)*n);
>     ans=fenzi(1,n+1);
>     printf("%lld\n",ans.res);
>     printf("%lld %lld\n",ans.l,ans.r);
> }
>     return 0;
> }

• 哪位大神看看我错哪里了，硬是找不到让我程序wa的数据啊。找了n久了，我用分治做的 (0) GDUT_LV 2014-07-22 10:36:10