#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;
}

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