Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Sequence Partitioning
Description Given a sequence of B), you have to partition it into several contiguous parts. Let _{i}p be the number of these parts, whose boundaries are (l_{1}, r_{1}), (l_{2}, r_{2}), ... ,(l, _{p}r), which satisfy _{p}l=_{i } r_{i − }_{1 }+ 1, l≤_{i } r, _{i}l_{1 }= 1, r= _{p }n. The parts themselves also satisfy the following restrictions:For any two pairs ( *A*,_{p}*B*), (_{p}*A*,_{q}*B*), where (_{q}*A*,_{p}*B*) is belongs to the_{p}*T*th part and (_{p}*A*,_{q}*B*) the_{q}*T*th part. If_{q}*T*<_{p}*T*, then_{q}*B*>_{p }*A*._{q}Let *M*be the maximum_{i}*A*-component of elements in the*i*th part, say*M*= max{_{i}*A*,_{li}*A*_{li+}_{1}, ...,*A*}, 1 ≤_{ri}*i*≤*p*it is provided that where Limit is a given integer.
Let B-components of elements in the ith part. Now I want to minimize the valuemax{ 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 ≤ 2 A_{1}, A_{2}, ..., A} ≤ Limit_{n}Output Output the minimum target value. Sample Input 4 6 4 3 3 5 2 5 2 4 Sample Output 9 Hint 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 B_{1} > A_{3}, B_{1} > A_{4}, B_{2} > A_{3}, B_{2} > A_{4}, max{A_{1}, A_{2}}+max{A_{3}, A_{4}} ≤ 6, and minimum max{B_{1}+B_{2}, B_{3}+B_{4}}=9.Source POJ Monthly--2007.07.08, Chen, Danqi |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator