# CFR 797 F. Mice and Holes ( DP, Monotonous, Divide and Conquer Optimization, or Deque Optimization )

Problem - F - Codeforces

1 ≤ N, M ≤ 5000
abs( X[ i ] ), abs( P[ i ] ) ≤ 1e9
C[ i ] ≤ 5000

dp[ i ][ j ]：已考慮完前 i 個洞且已部署前 j 個老鼠時，最小花費總和。
dp[ i ][ j ] = min{ dp[ i - 1 ][ k ] + cost[ j ] - cost[ k ], for all 0 ≤ j - k ≤ C[ i ] }

O( N * M )

// 2D / 1D Divide and Conquer Optimization O( N * M lg N )
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000;
const int MAXM = 5000;

int N, M;
int X[ MAXN ];
int P[ MAXM ], C[ MAXM ];

long long dp[ MAXM + 1 ][ MAXN + 1 ];
long long cost[ MAXN + 1 ];

void dvcq( int lv, int lb, int rb, int ql, int qr ) {
if( lb > rb ) return;
int mid = lb + rb >> 1;
int opt = mid;
for( int i = max( ql, mid - C[ lv - 1 ] ); i <= min( qr, mid ); ++i ) {
if( dp[ lv ][ mid ] > dp[ lv - 1 ][ i ] + cost[ mid ] - cost[ i ] ) {
dp[ lv ][ mid ] = dp[ lv - 1 ][ i ] + cost[ mid ] - cost[ i ];
opt = i;
}
}
dvcq( lv, lb, mid - 1, ql, opt );
dvcq( lv, mid + 1, rb, opt, qr );
}

signed main() {
ios::sync_with_stdio( 0 );
cin >> N >> M;
for( int i = 0; i < N; ++i ) {
cin >> X[ i ];
}
sort( X, X + N );
for( int i = 0; i < M; ++i ) {
cin >> P[ i ] >> C[ i ];
}
{ // dirty way to sort P[] and C[] by P
vector< int > ord( M );
vector< int > pvec( M ), cvec( M );
for( int i = 0; i < M; ++i ) {
ord[ i ] = i;
pvec[ i ] = P[ i ];
cvec[ i ] = C[ i ];
}
sort( ord.begin(), ord.end(), [ & ]( int i, int j ) { return P[ i ] < P[ j ]; } );
for( int i = 0; i < M; ++i ) {
P[ i ] = pvec[ ord[ i ] ];
C[ i ] = cvec[ ord[ i ] ];
}
}
memset( dp, 0x3f, sizeof( dp ) );
dp[ 0 ][ 0 ] = 0;
for( int i = 1; i <= M; ++i ) {
for( int j = 0; j < N; ++j ) {
cost[ j + 1 ] = cost[ j ] + abs( X[ j ] - P[ i - 1 ] );
}
dvcq( i, 0, N, 0, N );
}
if( dp[ M ][ N ] == 0x3f3f3f3f3f3f3f3fLL ) {
cout << -1 << endl;
} else {
cout << dp[ M ][ N ] << endl;
}
return 0;
}
// Deque Optimiation O( N * M )
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000;
const int MAXM = 5000;

int N, M;
int X[ MAXN ];
int P[ MAXM ], C[ MAXM ];

long long dp[ MAXM + 1 ][ MAXN + 1 ];

signed main() {
ios::sync_with_stdio( 0 );
cin >> N >> M;
for( int i = 0; i < N; ++i ) {
cin >> X[ i ];
}
sort( X, X + N );
for( int i = 0; i < M; ++i ) {
cin >> P[ i ] >> C[ i ];
}
{ // dirty way to sort P[] and C[] by P
vector< int > ord( M );
vector< int > pvec( M ), cvec( M );
for( int i = 0; i < M; ++i ) {
ord[ i ] = i;
pvec[ i ] = P[ i ];
cvec[ i ] = C[ i ];
}
sort( ord.begin(), ord.end(), [ & ]( int i, int j ) { return P[ i ] < P[ j ]; } );
for( int i = 0; i < M; ++i ) {
P[ i ] = pvec[ ord[ i ] ];
C[ i ] = cvec[ ord[ i ] ];
}
}
memset( dp, 0x3f, sizeof( dp ) );
dp[ 0 ][ 0 ] = 0;
for( int i = 1; i <= M; ++i ) {
deque< pair< long long, int > > dq;
vector< long long > cost( N + 1 );
for( int j = 0; j < N; ++j ) {
cost[ j + 1 ] = cost[ j ] + abs( X[ j ] - P[ i - 1 ] );
}
for( int j = 0; j <= N; ++j ) {
while( not dq.empty() and dq.back().first >= dp[ i - 1 ][ j ] + cost[ N ] - cost[ j ] ) {
dq.pop_back();
}
dq.emplace_back( dp[ i - 1 ][ j ] + cost[ N ] - cost[ j ], j );
while( j - dq.front().second > C[ i - 1 ] ) {
dq.pop_front();
}
dp[ i ][ j ] = dq.front().first - ( cost[ N ] - cost[ j ] );
}
}
long long ans = dp[ M ][ N ];
if( ans == 0x3f3f3f3f3f3f3f3fLL ) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
return 0;
}