如果您没有做过此题：
这是一道wqs二分（凸优化）套斜优

有两个问题：

• 1.凸优化的时候为什么需要从 $inf$ 开始，而设置为两倍最大斜率只有 $30\,pts$
• 2.为什么我写的确实是f[n]-l*m ，且斜优一直有等号，但还是像其它帖子一样 $\tt\color{red} WA$ 了（

已经尝试过：

• int128（ $90\,pts$ ）
• 全局long long（ $90\,pts$ ）
• 修改成和其他帖子一样的二分（ $20\,pts$ ）

现在占了一页了

求帮帮（

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;

#define ri register int
#define ll long long

#define Tp template<typename T>
#define g() getchar()
#define pc(x) putchar(x)
#define isdigit(x) (x>='0'&&x<='9')
namespace SlowIO{
	Tp inline void rd(T &x)	{
		x=0; char i=g(); bool f=1;
		while(!isdigit(i)) f&=(i!='-'),i=g();
		while(isdigit(i)) x=(x<<3)+(x<<1)+(i^48),i=g();
		x*=((f<<1)-1);
	}
	const int OUT=1e6;
    static char st[OUT]; int top;
    Tp inline void op(T x,char c=0){
        top=0; x<0&&(x=-x,putchar('-'));
        if(!x){ putchar(48); return; }
        while(x) st[++top]=x%10+48,x/=10;
        while(top) putchar(st[top--]);
        c&&putchar(c);
    }
	Tp inline void writeln(T x){ op(x);pc('\n'); }
	Tp inline void writesp(T x){ op(x); pc(' '); }
    Tp inline void write(T x,char c=0){ op(x); c&&pc(c); }
}; using namespace SlowIO;

#define N 100001
#define ldb long double
int n,m;
ll S[N],f[N],step[N];
inline ll sq(ll x){ return x*x; }
inline ll gx(int i){ return S[i]; }
inline ll gy(int i){ return f[i]+sq(S[i]-1)-1; }
const ldb oo=1e18;
inline ldb slope(int a,int b){
    register ll xa=gx(a),xb=gx(b);
    return (xb^xa)?(ldb)(gy(b)-gy(a))/(xb-xa):(gy(b)>gy(a)?+oo:-oo);
}
int q[N],l,r;
inline void pres(){
	//memset(f,0x7f,sizeof(f));
    f[0]=step[0]=0;
    q[l=r=1]=0;
}
inline bool solve(ll lim){
    pres();
    for(ri i=1;i<=n;++i){
        while(l<r&&slope(q[l],q[l+1])<=2*S[i]) ++l;
        f[i]=f[q[l]]+sq(S[i]-S[q[l]]+1)+lim,
        step[i]=step[q[l]]+1;
        while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) --r;
        q[++r]=i;
    } return step[n]>m;
//	for(ri i=1;i<=n;++i)
//	writesp(f[i]),writeln(step[i]);
//	write(step[n],'\n');
}

int main()
{
    rd(n),rd(m);
    for(ri i=1;i<=n;++i)
    rd(S[i]),S[i]+=S[i-1];
    register ll l=0,r=+oo,mid;
    while(l<r) mid=l+r>>1,(solve(mid)?l=mid+1:r=mid);
    solve(l); write(f[n]-l*m);
    return 0;
}