记录编号	407091	评测结果	WWWWWWWWWW
题目名称	[SDOI 2009] Bill的挑战	最终得分	0
用户昵称	Hzoi_Hugh	是否通过	未通过
代码语言	C++	运行时间	0.002 s
提交时间	2017-05-20 12:44:03	内存使用	7.92 MiB

#include<cstdio>
#include<queue>
#include<cstring>
#define MAXN 200005
using namespace std;
typedef long long LL;
typedef long double LD;
priority_queue<LL>Q;
LL t[MAXN],a[MAXN],s[MAXN],q[MAXN],head,tail,n,f[MAXN];
inline LD play(LL x,LL y)
{
   return (LD)((s[x]-s[y])/(x-y));
}
int main()
{
   freopen("set.in","r",stdin);
   freopen("set.out","w",stdout);
   /*scanf("%lld",&n);
   for(int i=1;i<=n;i++){scanf("%lld",&a[i]);s[i]=s[i-1]+a[i];t[i]=t[i-1]+i*a[i];}
   for(int i=1;i<=n;i++)
   {
      LL mid=(head+tail)>>1;
      while(1)
      {
         if(head==tail)
         {
            f[i]=t[i]+s[i]-s[q[mid]]-(i-q[mid]+1)*a[i];
            break;
         }
         if(mid==head)
         {
            if(play(q[mid+1],q[mid])>=(LD)a[i]) 
            {
              f[i]=t[i]+s[i]-s[q[mid]]-(i-q[mid]+1)*a[i];
              break;
            }
            mid=(mid+1+tail)>>1;
            continue;
         }
         if(mid==tail)
         {
            if(play(q[mid],q[mid-1])<=(LD)a[i]) 
            {
              f[i]=t[i]+s[i]-s[q[mid]]-(i-q[mid]+1)*a[i];
              break;
            }
            mid=(mid-1+head)>>1;
            continue;
         }
         if(play(q[mid],q[mid-1])<=(LD)a[i]&&play(q[mid+1],q[mid])>=(LD)a[i])
         {
            f[i]=t[i]+s[i]-s[q[mid]]-(i-q[mid]+1)*a[i];
            break;
         }
         if(play(q[mid],q[mid-1])>a[i])
         {
            mid=(mid+head)>>1;
            continue;
         }
         mid=(mid+tail)>>1;
      }
      Q.push(t[n]-t[i]+f[i]);
      while(head<tail&&play(i,q[tail])<play(q[tail],q[tail-1]))tail--;
      q[++tail]=i;
   }
   head=tail=0;
   memset(q,0,sizeof(q));
   for(int i=n;i>0;i--)
   {
      LL mid=(head+tail)>>1;
      while(1)
      {
         if(head==tail)
         {
            f[i]=t[n]-t[i-1]-(s[q[mid]]-s[i])+(q[mid]-i)*a[i];
            break;
         }
         if(mid==head)
         {
            if(play(q[mid],q[mid+1])<=(LD)a[i]) 
            {
              f[i]=t[n]-t[i-1]-(s[q[mid]]-s[i])+(q[mid]-i)*a[i];
              break;
            }
            mid=(mid+1+tail)>>1;
            continue;
         }
         if(mid==tail)
         {
            if(play(q[mid-1],q[mid])>=(LD)a[i]) 
            {
              f[i]=t[n]-t[i-1]-(s[q[mid]]-s[i])+(q[mid]-i)*a[i];
              break;
            }
            mid=(mid-1+head)>>1;
            continue;
         }
         if(play(q[mid-1],q[mid])>=(LD)a[i]&&play(q[mid],q[mid+1])<=(LD)a[i])
         {
            f[i]=t[n]-t[i-1]-(s[q[mid]]-s[i])+(q[mid]-i)*a[i];
            break;
         }
         if(play(q[mid-1],q[mid])<(LD)a[i])
         {
            mid=(mid+head)>>1;
            continue;
         }
         mid=(mid+tail)>>1;
      }
      Q.push(t[i-1]+f[i]);
      while(head<tail&&play(q[tail],i)>play(q[tail-1],q[tail]))tail--;
      q[++tail]=i;
   }
   LL ans=Q.top();
   printf("%lld",ans);
   while(1);*/
   return 0;
}