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 = 100010 ;
const int P = 110 ;
int n , m ;
int p ;
int q [ N ] ;
LL d [ N ] , t [ N ] ;
LL a [ N ] , s [ N ] ;
LL f [ P ] [ N ] ;
int h ;
int main ( ) {
cin > > n > > m > > p ;
for ( int i = 2 ; i < = n ; i + + ) cin > > d [ i ] , d [ i ] + = d [ i - 1 ] ; // 从2开始
for ( int i = 1 ; i < = m ; i + + ) cin > > h > > t [ i ] , a [ i ] = t [ i ] - d [ h ] , s [ i ] = s [ i - 1 ] + a [ i ] ;
sort ( a + 1 , a + m + 1 ) ; // 由小到大排序,m只小猫
// dp初始
memset ( f , 0x3f , sizeof f ) ;
for ( int i = 0 ; i < = p ; i + + ) f [ i ] [ 0 ] = 0 ; // 出动i个饲养员， ，
for ( int i = 1 ; i < = p ; i + + ) { // 饲养员
int hh = 0 , tt = 0 ; // 哨兵
for ( int j = 1 ; j < = m ; j + + ) { // 遍历小猫
// 凸包的斜率单调上升，并且，直线的斜率也是单调上升
// 准备在下凸壳中找到第一个斜率大于k的直线，
while ( hh < tt & & ( f [ i - 1 ] [ q [ hh + 1 ] ] + s [ q [ hh + 1 ] ] - f [ i - 1 ] [ q [ hh ] ] - s [ q [ hh ] ] ) < = a [ j ] * ( q [ hh + 1 ] - q [ hh ] ) )
hh + + ;
// 推出的公式
f [ i ] [ j ] = f [ i - 1 ] [ q [ hh ] ] + a [ j ] * ( j - q [ hh ] ) - ( s [ j ] - s [ q [ hh ] ] ) ;
// 维护下凸壳 [下面是 k=(y1-y2)/(x1-x)的PK， ， ，
while ( hh < tt & & ( f [ i - 1 ] [ j ] + s [ j ] - f [ i - 1 ] [ q [ tt ] ] - s [ q [ tt ] ] ) * ( q [ tt ] - q [ tt - 1 ] ) < = ( f [ i - 1 ] [ q [ tt ] ] + s [ q [ tt ] ] - f [ i - 1 ] [ q [ tt - 1 ] ] - s [ q [ tt - 1 ] ] ) * ( j - q [ tt ] ) )
tt - - ;
// 加入
q [ + + tt ] = j ;
}
}
cout < < f [ p ] [ m ] < < endl ;
return 0 ;
}
