打印文章 FZOJ 5190

传送门

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define ull unsigned long long

#define db double

#define N 1000100

#define jd (isdigit(c))

#define gg c=getchar()

#define inf 233333333333333

#define eps 1e-10

#define mod 1000000

#define ls k<<1

#define rs k<<1|1

#define root t[0].ch[1]

inline ll read()

{

    ll f=;bool x=;char gg;

    for(;!jd;gg)if(c=='-')x=;

    for(;jd;gg)f=(f<<)+(f<<)+(c&);

    return x?f:-f;

}

inline void write(ll x)

{

    if(x<)

    {

        putchar('-');

        x=~x+;

    }

    else if(!x)putchar('');

    char s[];

    int j=;

    for(;x;x/=)s[j++]=x%;

    for(int i=j-;~i;i--)putchar(s[i]+);

    putchar('\n');

}

ll n,l,dp[N],s[N],q[N],p[N];

inline db cal(ll x,ll y)

{

    return (s[x]==s[y])?1e100:(p[y]-p[x])*1.0/(s[y]-s[x]);

}

int main()

{

    while(~scanf("%lld%lld",&n,&l))

    {

        for(int i=;i<=n;i++)

        {

            ll c=read();

            s[i]=s[i-]+c;

        }

        ll head=,tail=;

        q[++tail]=;

        for(int i=;i<=n;i++)

        {

            while(head<tail)

            {

                db tk=cal(q[head],q[head+]);

                if(tk<*s[i])head++;

                else break;

            }

            ll j=q[head];

            dp[i]=dp[j]+(s[i]-s[j])*(s[i]-s[j])+l;

            p[i]=dp[i]+s[i]*s[i];

            while(head<tail&&cal(q[tail],i)<cal(q[tail-],q[tail]))tail--;

            q[++tail]=i;

        }

        write(dp[n]);

    }

    return ;

}

打印文章