#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 inline LL min(Re a,Re b){return aslope(Q[t-1],i))--t; Q[++t]=i; } printf("%lld",dp[n]); }