SEQPAR2 - Sequence Partitioning II
Given a sequence of N ordered pairs of positive integers (Ai, Bi), you have to partition it into several contiguous parts. Let p be the number of these parts, whose boundaries are (l1, r1), (l2, r2), ... ,(lp, rp), which satisfy li = ri-1 + 1, li <= ri, l1 = 1, rp = n. The parts themselves also satisfy the following restrictions:
For any two pairs (Ap, Bp), (Aq, Bq), where (Ap, Bp) is belongs to the Tpth part and (Aq, Bq) the Tqth part. If Tp < Tq, then Bp > Aq.
Let Mi be the maximum A-component of elements in the ith part, say
Mi = max {Ali, Ali+1 ... Ari}, 1 <= i <= p
it is provided that
where Limit is a given integer.
Let Si be the sum of B-components of elements in the ith part.
Now I want to minimize the value
max{Si:1 <= i <= p}
Could you tell me the minimum?
Input
The input contains exactly one test case. The first line of input contains two positive integers N (N <= 50000), Limit (Limit <= 231-1). Then follow N lines each contains a positive integers pair (A, B). It's always guaranteed that
max{A1, A2 ... An} <= Limit
Output
Output the minimum target value.
Example
Input: 4 6 4 3 3 5 2 5 2 4 Output: 9
Explanation
An available assignment is the first two pairs are assigned into the first part and the last two pairs are assigned into the second part. Then B1 > A3, B1 > A4, B2 > A3, B2 > A4, max{A1, A2}+max{A3, A4} <= 6, and minimum max {B1+B2, B3+B4}=9.
hide comments
Georeth Chow:
2016-08-22 16:07:40
A very nice problem.
|
Added by: | Bin Jin |
Date: | 2007-08-28 |
Time limit: | 0.109s-1.574s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: CPP |
Resource: | POJ Monthly--2007.07.08 |