1 #include <algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <string> 6 #include <cstdio> 7 #include <queue> 8 using namespace std ; 9 10 int n , k ;11 int sum[100006] , ans ;12 bool used[100006] ;13 struct node{14     int  id , val;15     bool operator < ( const node & a ) const {16         return a.val < val ;17     }18 };19 priority_queue < node > Q ;20 int las[100006] ,nxt[100006] ;21 22 inline void Init (   ) {23     freopen( "10344.in" , "r" , stdin ) ;24     freopen( "10344.out" , "w" , stdout ) ;25 }26 27 void input (   ) {28     scanf( "%d%d" , &n , &k ) ;29     int a ; scanf( "%d" ,&a ) ;30     int b ;31     for ( int x = 2 ; x <= n ; x++ ) {32         scanf( "%d" , &b ) ;33         node tep ;34         sum[ x ] = b - a ;35         las[x] = x - 1 , nxt[x] = x + 1 ;36 //        tep.val = sum[x] , tep.id = x ; 37         Q.push( node{ x , b - a } ) ;38         a = b ;39     }    40 }41 42 43 void sov(  ) {44     int tot = 0  ;45     sum[1] = sum[n+1] = (1<<30)-1;46     while( tot < k  ) {47         tot++ ;48         node tep ;49         while ( used[ Q.top( ).id ] ) Q.pop(  ) ;50         tep = Q.top( ) ; Q.pop( ) ;51         ans += tep.val ;52         int  l = las[ tep.id ]  , r = nxt[ tep.id ]  , v = sum[ l ] + sum[ r ] - sum[ tep.id ];53         sum[ tep.id ] = v ;54         Q.push( node { tep.id , v } ) ;55         if( l > 1 ) las[ tep.id ] = las[ l ] , nxt[ las[l] ] = tep.id , used[ l ] = true ;56         if( r <= n )nxt[ tep.id ] = nxt[ r ] , las[ nxt[r] ] = tep.id , used[ r ] = true ;57     }58 }59     60     61 void output(  ) {62     printf( "%d\n" , ans ) ;63 }64     65 66 int main (  ) {67 //    Init(  ) ;68     input(  ) ;69     sov(  ) ;70     output(  ) ;71 //    fclose(stdin);72 //    fclose(stdout);73     return 0 ;74 }