Submeter | Todas submissőes | Melhores | Voltar |
COWCARS2 - Cow Cars |
N (1 <= N <= 50,000) cows conveniently numbered 1..N are driving in separate cars along a highway in Cowtopia. Cow i can drive in any of M different high lanes (1 <= M <= N) and can travel at a maximum speed of S_i (1 <= S_i <= 1,000,000) km/hour.
After their other bad driving experience, the cows hate collisions and take extraordinary measures to avoid them. On this highway, cow i reduces its speed by D (0 <= D <= 5,000) km/hour for each cow in front of it on the highway (though never below 0 km/hour). Thus, if there are K cows in front of cow i, the cow will travel at a speed of max[S_i - D * K, 0]. While a cow might actually travel faster than a cow directly in front of it, the cows are spaced far enough apart so crashes will not occur once cows slow down as described,
Cowtopia has a minimum speed law which requires everyone on the highway to travel at a a minimum speed of L (1 <= L <= 1,000,000) km/hour so sometimes some of the cows will be unable to take the highway if they follow the rules above. Write a program that will find the maximum number of cows that can drive on the highway while obeying the minimum speed limit law.
Input
- Line 1: Four space-separated integers: N, M, D, and L
- Lines 2..N+1: Line i+1 describes cow i's initial speed with a single integer: S_i
Output
- Line 1: A single integer representing the maximum number of cows that can use the highway
Example
Input: 3 1 1 5 5 7 5
There are three cows with one lane to drive on, a speed decrease of 1, and a minimum speed limit of 5.
Output: 2
Two cows are possible, by putting either cow with speed 5 first and the cow with speed 7 second.
Adicionado por: | Wanderley Guimarăes |
Data: | 2008-06-06 |
Tempo limite: | 1s |
Tamanho do fonte: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Linguagem permitida: | ADA95 DOC ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE |
Origem: | USACO Open 2008 - Silver |