| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P173SUMG - ROUND 3G - Mùa đông đang tới |
Mùa đông đang đến với đất nước Vian, biết rằng nó kéo dài n ngày . Tồ là một người đam mê về các loại xe đạp và cậu mới được tặng một chiếc xe đạp cùng với hai bộ lốp dành cho mùa đông và mùa hè. Mỗi bộ lốp đều có thể sử dụng không quá k ngày(không cần liên tiếp). Bộ lốp mùa hè chỉ có thể dùng để đi vào những ngày nhiệt độ không âm còn bộ lốp mùa đông cậu có thể dùng cho bất kỳ nhiệt độ nào. Mỗi ngày trước khi đạp xe, Tồ có thể đổi 2 bộ lốp này với nhau nếu cần thiết. Biết rằng ban đầu xe đạp của Tồ gắn bộ lốp mùa hè.
Yêu cầu bạn hãy cách đổi 2 bộ lốp này ít lần nhất sao cho Tồ có thể đạp xe của mình an toàn và vui vẻ trong suốt mùa đông.
Input
-Dòng đầu tiên của đầu vào chứa hai số nguyên n, k (1 ≤ n ≤ 2x105; 0 ≤ k ≤ n)
-Dòng thứ hai chứa n số nguyên Ti (-20 <= Ti <= 20) là nhiệt độ trung bình của ngày thứ i.
Output
Ghi ra số lần nhỏ nhất Tồ phải đổi giữa 2 cặp lốp với nhau để có thể duy trì việc đạp xe hết mùa đông . Nếu không thể, ghi ra -1.
Example
Test 1
Input: 4 3
-5 20 -3 0
Output: 2
Test 2
Input:
4 2
-5 20 -3 0
Output:
4
Test 3
Input:
10 6
2 -5 1 3 0 0 -4 -3 1 0
Output:
3
Giải thích:
Test 1: Ngày đầu tiên, Tồ đổi lốp mùa hè sang mùa đông và dùng nó đến hết ngày thứ ba sau đó cậu lại chuyển từ lốp mùa đông sang mùa hè để đi hết ngày cuối cùng.
Test 2: Mỗi ngày Tồ lại chuyển về bộ lốp tương ứng để đi được trong điều kiện nhiệt độ đã cho.
| Được gửi lên bởi: | adm |
| Ngày: | 2017-07-28 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
