| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
C11DK1 - Những chiếc lá mùa thu |
“Hà Nội mùa thu, cây cơm nguội vàng, cây bàng lá đỏ, nằm kề bên nhau phố xưa nhà cổ, mái ngói thâm nâu. ... Hà Nội mùa thu! Đi giữa mọi người, lòng như thầm hỏi "tôi đang nhớ ai?", sẽ có một ngày trời thu Hà Nội, trả lời cho tôi, sẽ có một ngày từng con đường nhỏ trả lời cho tôi.”
Ngày 7-10-2011, khaihanhdk tặng ĐK
Mỗi năm đến mùa thu, những chiếc lá vàng lại rơi khắp trên đường làng, nơi mà khaihanhdk đang ở. Do lần đầu tiên xếp hạng cuối lớp, thầy chủ nhiệm đã phạt khaihanhdk phải quét hết lá vàng rơi trên con đường làng trước ngày 7-10. Nhưng đã học tệ rồi, lại còn thêm tính lười biếng. Cuối cùng, ngày 6-10 cũng đã đến, nhưng khaihanhdk vẫn chưa quét được chiếc lá vàng nào, khaihanhdk cứ ngồi khóc mãi, khóc mãi. Bỗng một lúc sau, Bụt hiện ra và hỏi: “Kìa con, vì sao con khóc?”.
Khaihanhdk kể lại hết câu chuyện cho Bụt nghe, Bụt nói: “Ờ, ta hiểu rồi, ta chỉ có một cách để giúp con. Con hãy ra cửa hàng Olympic Tin học Việt Nam (VNOI), con mua vài chiếc máy hút lá vàng do cựu học sinh Nguyễn Vương Linh vừa đem hàng từ Thái Lan về. Vấn đề bây giờ là con phải biết cách chọn lựa máy nào cho tốt mà ít tốn kém đấy nhé. Nếu con không biết có thể hỏi các coder trên trang web vnoi.info, có thể họ sẽ có cách giúp con. Thôi, ta đi đây.”
Con đường làng là 1 đường thẳng, trên đó mỗi chiếc lá vàng có tọa độ x[i], có không quá n (n <= 10^4) chiếc lá vàng trên đường.
Cửa hàng có m (m <= 10^4) loại máy, có thể mua nhiều cái máy cùng 1 loại, không giới hạn số lượng. Mỗi loại máy có 2 thông số là:
d[i]: nếu đặt máy i ở vị trí x thì nó sẽ hút được tất cả các lá vàng có tọa độ nằm trong khoảng [x – d[i], x + d[i]].
c[i]: chi phí để mua máy.
Yêu cầu: Cần đặt một số máy lên đường làng sao cho các máy hút hết được lá vàng và chi phí mua máy là thấp nhất.
Input
Dòng đầu gồm 2 số: n và m.
N dòng tiếp theo: mỗi dòng ghi số x[i] (abs(x[i]) <= 10^9).
M dòng tiếp thep: mỗi dòng ghi 2 số: d[i] và c[i] (1 <= d[i] <= 10^9, c[i] <= 1000).
Output
Chi phí nhỏ nhất tìm được.
Example
Input:
5 3
2
8
3
6
9
7 9
2 3
8 6
Output:
6
| Được gửi lên bởi: | Duy Khanh Nguyen |
| Ngày: | 2011-10-06 |
| Thời gian chạy: | 0.605s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC GAWK MAWK BC C-CLANG C NCSHARP CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PAS-GPC PAS-FPC PICO PROLOG PYPY3 PY_NBC R RACKET CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
| Nguồn bài: | Ý tưởng chưa có lời giải |
hide comments
|
2017-11-12 10:06:12
oh yeah, sảng khoái quá, mình nghĩ mình k thể làm được bài này cơ, thanh bác comment cuối nhé ^^ {dinh truong lam} |
|
|
2016-09-27 03:35:58
Code: http://shink.in/3hTzR |
|
|
2014-07-10 17:41:21 Lollipop
Code lòi mắt mới Ac, toàn TLE :)) Last edit: 2014-07-10 18:10:46 |
|
|
2014-07-01 10:56:52 Tây Cuồng
Mặc dù đã ac nhưng thời gian chạy là 10.7s, không biết anh (chị) Bit với anh (chị) Cottontail Tee làm cách nào mà chương trình chạy nhanh thế nhỉ? Last edit: 2014-07-01 10:57:37 |
|
|
2014-06-30 21:07:48 Nắng
đpt >10^8 vẫn AC :D may quá ^^ |
|
|
2013-06-05 09:23:32 an IM3 Ex-Member of Bit
QHD 10^7 --> AC :D |
|
|
2013-06-04 06:03:24 Cottontail Tee
chú ý giới hạn c[i] là AC :D |
RSS