You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
# include <bits/stdc++.h>
using namespace std ;
typedef long long LL ;
const int N = 300010 ;
int n , s ;
LL t [ N ] , c [ N ] , f [ N ] ;
int q [ N ] ;
int main ( ) {
cin > > n > > s ;
for ( int i = 1 ; i < = n ; i + + ) cin > > t [ i ] > > c [ i ] , t [ i ] + = t [ i - 1 ] , c [ i ] + = c [ i - 1 ] ;
// 初始化队列
int hh = 0 , tt = 0 ; // 添加哨兵
for ( int i = 1 ; i < = n ; i + + ) { // 动态规划, 从小到大枚举每个i
int l = hh , r = tt ;
// 通过二分upper_bound, 找到第一个斜率大于k=st[i] + S的两个点,起点就是切点
while ( l < r ) {
int mid = ( l + r ) / 2 ;
// check函数
if ( f [ q [ mid + 1 ] ] - f [ q [ mid ] ] > ( t [ i ] + s ) * ( c [ q [ mid + 1 ] ] - c [ q [ mid ] ] ) )
r = mid ;
else
l = mid + 1 ;
}
int j = q [ l ] ; // 切点位置
// 动态规划
f [ i ] = f [ j ] - ( t [ i ] + s ) * c [ j ] + t [ i ] * c [ i ] + s * c [ n ] ;
// 出队尾,斜率比自己大的点都要出凸包队列,小心long long的乘法
while ( hh < tt & & ( __int128 ) ( f [ q [ tt ] ] - f [ q [ tt - 1 ] ] ) * ( c [ i ] - c [ q [ tt - 1 ] ] ) > = ( __int128 ) ( f [ i ] - f [ q [ tt - 1 ] ] ) * ( c [ q [ tt ] ] - c [ q [ tt - 1 ] ] ) )
tt - - ;
q [ + + tt ] = i ;
}
cout < < f [ n ] < < endl ;
return 0 ;
}