# CFR 158 E. Phone Talks ( DP )

Problem - E - Codeforces

The first input line contains a pair of integers n, k (0 ≤ k ≤ n ≤ 4000) separated by a space. Following n lines contain the description of calls for today. The description of each call is located on the single line and consists of two space-separated integers ti and di, (1 ≤ ti, di ≤ 86400). All ti are distinct, the calls are given in the order of strict increasing ti.
Scheduled times of calls [ti, ti + di - 1] can arbitrarily intersect.
TL: 3000 ms
ML: 256 MB

dp[ i ][ j ]：已考慮前 i 通電話，已無視 j 通電話，此時 i - j 通電話結束後的第一個空閑時間。
dp[ i ][ j ] = min( dp[ i - 1 ][ j - 1 ], max( dp[ i - 1 ][ j ], T[ i - 1 ] ) + D[ i - 1 ] )

O( N * K )

```int N, K;
vi T, D;

void init(){
cin >> N >> K;
if( N == 0 ){
cout << 86400 << endl;
exit( 0 );
}
T = D = vi( N );
for( int i = 0; i < N; ++i ){
cin >> T[ i ] >> D[ i ];
}
}

vvi dp;

void preprocess(){
dp = vvi( N + 1, vi( K + 1, INF ) );
dp[ 0 ][ 0 ] = 1;
for( int i = 0; i < N; ++i ){
for( int j = 0; j <= K; ++j ){
if( j + 1 <= K ){
upmin( dp[ i + 1 ][ j + 1 ], dp[ i ][ j ] );
}
upmin( dp[ i + 1 ][ j ], max( dp[ i ][ j ], T[ i ] ) + D[ i ] );
}
}
}

void solve(){
int ans = 86400 - dp[ N ][ K ] + 1;
for( int i = 0; i < N; ++i ){
upmax( ans, T[ i ] - dp[ i ][ min( i, K ) ] );
}
cout << ans << endl;
}
```