Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MINROAD - VOI 2014 - Con duong Tung Truc

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/minroad


Địa điểm du lịch Dailai nổi tiếng với con đường Tùng-Trúc. Đó là một con đường dài và thẳng, dọc bên đường người ta trồng rất nhiều cây tùng và cây trúc. Với mục đích tạo điểm nhấn cho con đường, Ban quản lý khu du lịch muốn chọn một đoạn đường mà dọc theo nó có ít nhất a cây tùng và có ít nhất b cây trúc để trang trí. Sau khi khảo sát, Ban quản lý ghi nhận được vị trí của từng cây tùng và cây trúc. Trên con đường có tất cả n cây, không có hai cây nào ở cùng một vị trí. Cây thứ i ở ị trí có khoảng cách đến vị trí bắt đầu của con đường là d_i (i = 1, 2, ..., n). Với kinh phí có hạn, Ban quản lý muốn chọn một đoạn đường thỏa mãn điều kiện đã nêu với độ dài là ngắn nhất.

Yêu cầu

Cho a, b và vị trí của n cây. Hãy tìm đoạn đường có độ dài ngắn nhất mà dọc theo đoạn đường đó có ít nhất a cây tùng và b cây trúc.

Input

  • Dòng đầu chứa 3 số nguyên dương n, a, b (a + b <= n)
  • Dòng thứ i trong n dòng tiếp theo mỗi dòng chứa hai số nguyên dương d_i (d_i <= 10^9) trong đó d_i là khoảng cách của cây tính từ vị trí bắt đầu của con đường, k_i = 1 nếu cây thứ i là cây tùng, k_i = 2 nếu là cây trúc.
  • Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Ghi ra một số nguyên là độ dài đoạn đường ngắn nhất tìm được, quy ước ghi số -1 nếu không tồn tại đoạn đường nào thỏa mãn điều kiện đặt ra.

Giới hạn

  • d_i <= 10^9.
  • 30% số test có n <= 300.
  • 30% số test khác có n <= 3000.
  • 40 % số test còn lại có n <= 300000.

Example

Input:
7 2 2
20 2
30 1
25 1
35 1
60 2
65 2
10 1

Output:
35

Được gửi lên bởi:VOJ Team
Ngày:2014-01-04
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:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VOI 2014

hide comments
2017-07-24 04:12:46
:V quên ghi -1 => 92.5
2 đấm AC :<
2016-09-23 09:49:53
tại sao lại ra 35
2016-09-11 10:52:44
sao đáp án lại là 35 vậy. không phải 25 sao?
2016-01-04 13:26:56
THAM KHẢO TẠI https://traitaodo.wordpress.com/2016/01/04/voi-2014-con-duong-tung-truc-minroad/
2016-01-02 14:34:36 Lê Trần Hữu Ðắc
quên ghi -1 đc 92.5 ảo vãi!!
2015-11-22 17:29:46
bài này cũng đc cho thi VOI ==

2015-10-22 16:43:56 The Legendary Tiger (NDHD)
tham khảo tại https://copcode.wordpress.com/2015/07/30/minroad-spoj-voi-2014-day-1-con-duong-tung-truc/

Last edit: 2015-10-22 16:44:18
2015-10-04 12:22:20 Hacking to the Gate
Lỡ sub code chạy từ 4->n mà cũng được 92.5, test yếu chăng?
2014-12-30 18:05:12 The Flash
bài này sort cái độ dài trc, sau đó dùng binary search n-(a+b)+1 lần ( ứng với từng ấy cây có thể là 1 đầu mút của đoạn) đề tìm điểm mút còn lại
sẵn khoe mới ac luôn :v
2014-12-18 00:51:56 ChienTran
A cmn C :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.