BZOJ-3156: 防御准备

Description

1<=N<=10^6,1<=Ai<=10^9

斜率优化裸题。f数组少开了个0。。GG RE+1

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,a[1001000],q[1001000];
ll f[1001000];
inline ll k(int x){return -x;}
inline ll b(int x){return f[x]+1ll*x*(x+1)/2;}
int main()
{
    scanf("%d",&n); int i;
    for(i=1;i<=n;++i) scanf("%d",a+i);
    int h=1,t=1;
    for(i=1;i<=n;++i)
    {
        while(h<t&&k(q[h])*i+b(q[h])>=k(q[h+1])*i+b(q[h+1])) h++;
        f[i]=k(q[h])*i+b(q[h])+a[i]+1ll*i*(i-1)/2;
        while(h<t&&( b(i)-b(q[t]) )*(k(q[t-1])-k(q[t]) ) <= ( b(q[t])-b(q[t-1]) )*( k(q[t])-k(i) )) t--;
        q[++t]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}