Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
SAILS - IOI07 Sails |
English | Vietnamese |
Bọn cướp biển đang đóng một chiếc tàu mới. Chiếc tàu này có N cột buồm chia thành các đoạn độ dài đơn vị, độ cao của một cột buồm bằng số đoạn thẳng trên cột buồm. Mỗi cột buồm có một số lá buồm, mỗi lá buồm nằm gọn trên một đoạn độ dài đơn vị. Các lá buồm trên một cột có thể được phân bố tùy ý vào các đoạn khác nhau trên cột buồm, nhưng mỗi đoạn chỉ được chứa đúng một lá buồm.
Mỗi cách sắp đặt lá buồm khác nhau sẽ tạo ra một lực đẩy gió khác nhau khi thuyền ra khơi. Các lá buồm đằng trước các lá buồm khác ở cùng độ cao sẽ nhận được ít gió hơn và tạo ít lực đẩy hơn. Với mỗi lá buồm, ta định nghĩa độ kém hiệu quả của nó là tổng số lá buồm có cùng độ cao ở phía sau nó. Chú ý là "phía trước" và "phía sau" phụ thuộc vào hướng của con thuyền: trong hình vẽ dưới đây, "phía trước" nghĩa là ở bên trái, "phía sau" nghĩa là ở bên phải.
Độ kém hiệu quả của cả con thuyền là tổng độ kém hiệu quả của mỗi lá buồm.
Con thuyền này có 6 cột buồm, với độ cao 3, 5, 4, 2, 4 và 3 từ phía trước (bên trái của hình vẽ) đến phía sau.
Cách sắp xếp các lá buồm này cho độ kém hiệu quả là 10. Độ kém hiệu quả của mỗi lá buồm được ghi trên lá buồm đó trên hình vẽ.
Yêu cầu
Viết chương trình nhập vào độ cao và số lá buồm trên mỗi trong số N cột buồm, xác định độ kém hiệu quả nhỏ nhất có thể của con thuyền.
Dữ liệu
Dòng đầu tiên chứa một số nguyên N (2 ≤ N ≤ 100 000), số cộ buồm của con thuyền.
Mỗi trong số N dòng tiếp theo chứa hai số nguyên H và K (1 ≤ H ≤ 100 000, 1 ≤ K ≤ H), độ cao và số lá buồm trên cột buồm tương ứng. Các cột buồm được cho theo thứ tự từ phía trước đến phía sau của con thuyền.
Kết quả
In ra một số nguyên duy nhất, độ kém hiệu quả nhỏ nhất cỏ thể của con thuyền.
Chú ý: dùng kiểu số nguyên 64 bit để tính và in kết quả (long long trong C/C++, int64 trong Pascal).
Ví dụ
Dữ liệu 6 3 2 5 3 4 1 2 1 4 3 3 2 Kết quả 10
Được gửi lên bởi: | Jimmy |
Ngày: | 2008-12-13 |
Thời gian chạy: | 0.200s |
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ừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET |
Nguồn bài: | IOI 2007 - Croatia |