| Submit | All submissions | Best solutions | Back to list |
LOGGING - Logging |
Gần nhà Beo có một dãy rừng gỗ quý gồm n cây được đánh số từ 1 đến n và mỗi cây có một giá trị k. Beo sắp cưới vợ nên muốn chọn một số cây chặt để bán lấy tiền. Nhưng Beo là một người rất yêu thiên nhiên anh không muốn hủy hoại hết dãy rừng nên anh sẽ không bao giờ chặt hai cây đứng cạnh nhau và trong dãy rừng có một số cây thuộc giống sắp tiệt chủng có giá trị k < 0 nếu chặt phải Beo sẽ bị nộp một khoản tiền bằng trị tuyệt đối giá trị của cây. Beo muốn có một đám cưới hoành tráng nên cần một khoản tiền càng lớn càng tốt, hãy giúp Beo chọn các cây để bán được nhiều tiền nhất.
There is a row of precious timber forests of n trees numbered from 1 to n and each tree has a monetary value of k. Leo is about to get married, so he wants to choose some cut trees to sell for money. But he is a person who loves nature very much, he does not want to destroy all the forests, so he complies with 2 conditions:
- Never cut down two consecutive trees
- There are some trees of the rare species with the value k < 0, if the Beo is cut down, he will be fined a mount of money which is equal the absolute value of that tree.
Calculate the maximum amount of money Beo can earn.
Input
The first line contains a single integer n (1≤ n ≤ 105)
The next line contains n integers ki (1≤ i ≤ n , |k| ≤ 109) -value of each tree.
Output
A single integer, the maximum amount that Beo can get.
Example
Input: 6 3 1 3 3 2 2 Output: 8
| Added by: | Ha Minh Ngoc |
| Date: | 2015-05-22 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG FSHARP GO JAVA JS-MONKEY NODEJS PHP PYTHON PYPY PYPY3 PYTHON3 RUBY SQLITE SWIFT VB.NET |
RSS