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: Undergraduate Instruction Evaluation
Description Inspectors from the Ministry of Education are coming to frkstyc’s university to evaluate its undergraduate instruction. Although the university is among the best ones in the country, the dean office rules that there is still room for improvement. Now they have produced a list of points of possible improvement, such as trimming the trees and lawns on the campus and lowering the rate of late arrivals at classes. Improvement is good, whereas overdoing that is not. Nicely tidied dormitories are certainly eyeball-catching. But if they gets extravagantly decorated, they will be dimmed solely as evidence of affectation for sure. With the evaluation program in hand, the dean office has to decide how much effort to spend on each point of improvement so that the university will score in extra as high as possible without the inspectors perceiving any pretence. Input The input consists of a single test case. The first line contains two integers y (1 ≤ _{i}x ≤ _{i}y ≤ _{i}n). The first of the remaining two lines contains n integers b (0 ≤ _{i}b ≤ 2000); the second contains _{i}m integers c (0 ≤ _{i}c ≤ _{i}The input is interpreted as follows. The dean office has listed y (inclusive) sum to over _{i}c, some inspector will believe what he/she has seen is deliberate and unnatural. The total extra score is calculated as the weighted sum of score increase in each point with the _{i}b’s as the weights._{i}Output Output the highest possible total extra score. It is guaranteed to be bounded. Sample Input 5 4 2 4 1 4 3 4 1 1 1 2 5 12 10 6 1 1 1 1 1 Sample Output 12 Hint If two linear programs minimize subject to
,b ≥ x0and maximize subject to
,c ≥ y0are both feasible, then *, the optimal solutions to them respectively, satisfy that yc^{T} = xb^{T}.ySource |

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

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

Any problem, Please Contact Administrator