#include #include #include #define LL long long #define Re register LL const int N=3e3+5; LL p,i,j,n,m,h,t,Q[N],S[N],dp[N][N]; //S_walk[m]=S[n] // m m // i=1 i=1 // m // i=1 //dp[p][i]=min(dp[p-1][j]+(S[i]-S[j])^2) //(2*S[i]) * S[j] + (dp[p][i]-S[i]^2) = (dp[p-1][j]+S[j]^2) // k * x + b = y inline LL min(Re a,Re b){return aslope(Q[t-1],i))--t; Q[++t]=i; } } printf("%lld",m*dp[m][n]-S[n]*S[n]); }