One day, a terrible fire is started in the forest where the fox and wolf families live (probably by jealous, inferior humans). The animals can easily escape harm themselves - however, they wish to save as many trees as they can. Naturally, the foxen can put out fires with their tails, however this can only be done at a rate of one tree per minute.
The forest consists of a single row of N (1 ≤ N ≤ 1,000,000,000) trees, which the foxen have numbered from 1 to N from left to right. Each tree is in contact with the trees immediately to its left and right.
At the beginning, M (1 ≤ M ≤ 5000 and 1 ≤ M ≤ N) different trees are set on fire. At the end of every minute after that, each untouched tree that is next to any burning trees catches on fire itself. It takes one minute for a tree to burn down entirely.
During each minute (including right after the trees are initially set on fire), the foxen can choose a single tree to brush their tails. This tree stops burning immediately (if it's currently on fire), and due to the amazing properties of fox tails, becomes impervious to fire forever.
The process continues until not a single tree is on fire, at which point the foxen don't even need to count how many trees are still standing, seeing as they calculated it when they first detected the forest fire. The foxen have of course acted so as to maximize the number of trees preserved, so the question is… how many is that?
|Line 1:||Two integers — N and M|
|The next M lines:||The integer Ti, indicating that tree Ti is initially set on fire|
A single integer - the maximum number of trees that the foxen can save from being burnt down.
9 3 3 2 8
The forest initially looks like this, with burning trees represented by '
*', burnt-down trees by '
x', and protected trees by '
1 * * 4 5 6 7 * 9
The foxen put out the fire at tree 8 during the first minute, while the other fires spread:
* x x * 5 6 7 P 9
The foxen now put out tree 4, and the other fire has nowhere to go:
x x x P 5 6 7 P 9
In the end, 3 trees have burned down, leaving 6 standing.
Point Value: 25 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Mar 20, 2009
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3