1846679_ce.cc

北大大牛代码 1240道题的原代码 超级权威

#include <iostream>
using namespace std;

int64 n, a[200001];

int64 min(int64 i,int64 j)
{
 int64 li,s;
 s = a[i];
 if(i == j) return s;
 for(li = i + 1; li <= j; li++)
  if(a[li] < s)
  s = a[li];
  return s;
}

int64 sum(int64 i,int64 j)
{
  int64 s; int64 li;
  s = a[i];
  for(li = i + 1; li <= j; li++)
  s += a[li];
  return s;
}

int64 f(int64 i,int64 j)
{
  return (sum(i,j) * min(i,j));
}
int main()
{
  int64  s, t,  ma, mb, mm, nn;
  int64 li, lj;
  int64 max1,tmp,max;
  max = mm = nn = -1;
  cin>>n;
  for(li = 0; li < n; li++)
   scanf("%ld",&a[li]);

  for(li = 0; li <n; li++)
    {
     tmp = max1 = a[li] * a[li]; 
     for(lj = li + 1; lj < n; lj++)
     {
	 s = min(li,lj-1);
	 t = sum(li,lj);
     if(a[lj] >= s) {tmp = f(li,lj);if(tmp >= max1) max1 = tmp; ma = li; mb = lj; continue;}
     if(t * a[lj] >= (t - a[lj]) * s ) {tmp = f(li,lj);if(tmp >= max1) ma = li; mb = lj;max1 = tmp;}
     }
	if( max1 >= max)
    {max = max1;mm = ma;nn = mb;}
    }
  cout<<max<<endl;
  cout<<mm+1<<" "<<nn+1<<endl;
  
  return 0;
}