#include #include #define LL long long #define Re register LL const int N=3e5+5; LL i,j,n,h=1,t=0,S,Q[N],ST[N],SF[N],dp[N]; //dp[p][i]=min(dp[p-1][j]+(ST[i]+S*p)*(SF[i]-SF[j])); //dp[i]=dp[j]+ST[i]*(SF[i]-SF[j])+S*(SF[n]-SF[j]); //(S+ST[i]) * SF[j] + (dp[i]-ST[i]*SF[i]-S*SF[i]) = (dp[j]) // k * x + b = y //ti� 均>0,且ST[i]是单调递增 inline LL min(Re a,Re b){return a=Y(i)?1e18:-1e18):(long double)(Y(j)-Y(i))/(X(j)-X(i));} inline LL sakura(Re k){ if(h==t)return Q[h]; Re l=h,r=t; while(l>1,i=Q[mid],j=Q[mid+1]; if(slope(i,j)=slope(Q[t-1],i))--t; Q[++t]=i; } printf("%lld",dp[n]); }