|Online Judge||Problem Set||Authors||Online Contests||User|
We're Going In
As the standoff with Empire's Army continues, the Commander of Union, Yang, finally loses his patience. He intends to send a troop going through the long straight blockade line secretly and spying into enemy's activities.
After several days' observation, the Commander finds the following facts:
The whole break-through will last T seconds. To make sure the action successes, Yang wants to maximize the average uncovered length during the T seconds. In another word, assuming the function f(t) indicating the uncovered length of the blockade line at time t. Yang wants to maximize the definite integral:
The first line of input contains four integers, L, R, N, T (0 ≤ L, R, T ≤ 1000000), (0 ≤ N ≤ 100).
The following N lines describe the soldiers. Each line consists of two integers, x (0 ≤ x ≤ L) and d. x indicates the initial position of the soldier and d indicates the direction of soldier's movement. The soldier moves to the end with x = L when d = 1 and to the end with x = 0 when d = -1.
Output the maximum I(x) with three digits after the decimal point.
10 1 1 3 1 1
POJ Monthly Contest – 2009.02.22, Dagger
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
Any problem, Please Contact Administrator