| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
KPLANK - Bán dừa |
Nếu các bạn biết câu chuyện thương tâm "ăn dưa leo trả vàng" của Pirate hẳn đã phải khóc hết nước mắt khi anh ấy, vì lòng thương chim, đã bán rẻ trái dưa leo siêu bự của mình.
Dưa leo cũng đã bị chim to lấy đi rồi, Pirate giờ chuyển sang nghề bán dừa để bù lỗ. Bất đắc dĩ thôi, vì trên đảo toàn là dừa...
Nhưng mà bán cái gì thì đầu tiên cũng phải có biển hiệu đã. Pirate quyết định lùng sục trên đảo các mảnh ván còn sót lại của những con tàu đắm để ghép lại thành tấm biển. Cuối cùng anh cũng tìm được N tấm ván hình chữ nhật, tấm thứ i có chiều rộng là 1 đơn vị và chiều dài là ai đơn vị. Pirate dựng đứng chúng trên mặt đất và dán lại với nhau để được một mảnh ván to hơn (xem hình minh họa).
Việc cuối cùng chỉ là đem mảnh ván này đi cưa thành tấm biển thôi. Nhưng hóa ra đây lại là công việc khó khăn nhất. Pirate rất thích hình vuông và muốn tấm biển của mình càng to càng tốt, nhưng khổ nỗi trên đảo lại không có nhiều dụng cụ đo đạc. Không êke, không thước đo độ, nên Pirate chỉ còn cách dựa vào cạnh của N tấm ván ban đầu để cưa cho thẳng thôi. Pirate chỉ có thể cưa theo những đoạn thẳng chứa một cạnh nào đó (dọc hoặc ngang) của các tấm ván.
Hãy giúp anh ấy cưa được tấm biển lớn nhất có thể.
Input
- Dòng thứ nhất: ghi số nguyên N - số tấm ván.
- N dòng tiếp theo: mô tả độ cao của các tấm ván theo thứ tự trái sang phải sau khi đã dán lại.
Output
- Một số nguyên duy nhất là độ dài cạnh của tấm biển lớn nhất có thể cưa được.
Giới hạn
- Độ cao của các tấm ván là các số nguyên dương không vượt quá 109.
- 1 ≤ N ≤ 106.
- 60% số test có 1 ≤ N ≤ 2000.
- 80% số test có 1 ≤ N ≤ 105.
Example
Input: 7
5
2
4
3
3
1
4
Output: 3
Giải thích: Hình dưới đây minh họa phương án tối ưu.
| Được gửi lên bởi: | khanhptnk |
| Ngày: | 2011-06-26 |
| Thời gian chạy: | 0.400s |
| 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 SCM guile SED |
hide comments
|
|||||||||
|
2021-05-27 18:01:15
Tham khảo: https://vnspoj.github.io/problems/KPLANK |
|||||||||
|
2020-08-04 10:32:02
Nếu bạn nào được 53.33 điểm thì nhớ thử test này: 6 5 5 5 5 1 3 đáp án sẽ ra 1 nha không phải 4 đâu! From: Dung T1k28 :))) Còn ai không hiểu tại sao như thế thì vì trong đề có câu" Pirate chỉ còn cách dựa vào cạnh của N tấm ván ban đầu để cưa cho thẳng thôi."Có nghĩa là phải cưa theo mép trên của một tấm nào đó :)) |
|||||||||
|
2020-05-08 06:16:11
Bài này dùng stack, không nói nhiều :> |
|||||||||
|
2020-02-26 02:45:05
bạn nào 80đ đọc kĩ lại n <= 10^6 nhé |
|||||||||
|
2019-09-23 04:17:50
duonght_pro_xinhgainhathemattroi_:) hahahahahahahahahahahahaha |
|||||||||
|
2019-07-12 17:22:18
huhu làm k nhìn kĩ n=10^6 mất mấy đấm ac :((( |
|||||||||
|
2019-07-04 21:39:39
bài này chú ý là cắt theo độ cao nha :v |
|||||||||
|
2019-06-24 04:40:04
Nếu ai làm deque và tính mãi nhưng không ra thì để ý là kết quả không phụ thuộc nặng vào L và R, mà phụ thuộc vào giá trị độ cao của tấm ván |
|||||||||
|
2019-05-17 10:29:47
Nếu bạn nào được 53.33 điểm thì nhớ thử test này: 6 5 5 5 5 1 3 đáp án sẽ ra 1 nha không phải 4 đâu! From: Dung T1k28 :))) |
|||||||||
|
2019-05-16 09:36:48
In ra 0 vẫn full mà :)))) |
|||||||||
RSS