GRAPE - Trồng nho
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Vào năm 2050, nho trở thành trái cây được ưa chuộng nhất. Rượu nho, nho tươi, nho khô, kẹo trái cây vị nho, … được tiêu thụ với số lượng cực lớn. Bởi thế ngành trồng và chế biến sản phẩm từ nho thu lãi rất cao. Tập đoàn RICH, sau khi đã thành công trong vụ đầu tư vào khu đất “vàng” ở Sài Gòn, quyết định lấn sang lĩnh vực trồng nho.Ban giám đốc RICH quyết định sẽ đầu tư thuê một khu đất lớn ở Phan Rang – vùng trồng nho tốt nhất Việt Nam. Sở dĩ phải thuê vì RICH đã bỏ nhiều tiền để mua khu đất “vàng”.
Vùng đất nông nghiệp ở Phan Rang được chia thành các block –một khu đất hình vuông diện tích 1 hecta. Do vị trí địa lí đặc biệt (phía Đông giáp biển, phía Tây là các dãy núi)nên độ cao trung bình của các block đất ở Phan Rang có tính chất không giảm theo chiều từ Đông sang Tây và từ Bắc xuống Nam. Vùng đất nông nghiệp có thể được biểu diễn bằng một bảng H kích thước M dòng, N cột, mỗi ô biểu diễn độ cao của 1 block đất. Ô (1,N) ở phía Đông Bắc còn ô (M,1) ở phía Tây Nam. Ví dụ với M=4 và N=5 :
34 33 25 21 13 35 35 33 21 16 50 45 33 33 16 93 83 66 51 23
RICH có Q giống nho. Giống nho i được đặc trưng bởi 2 chỉ số L i và R i chỉ có thể được trồng trên các block đất có độ cao trung bình trong đoạn [L i ,R i ]. Ban lãnh đạoRICH muốn biết với mỗi giống nho, diện tích khu đất lớn nhất có thể trồng đượclà bao nhiêu. Giả sử RICH chỉ mua một khu duy nhất và khu này là một hình vuông gồm các block đất liên tiếp, có các cạnh song song với hướng Đông-Tây và Bắc-Nam. Ví dụ : với giống nho có L=20, R=90 thì khu đất lớn nhất gồm các ô được tô đậm trên hình.
Input
Dòng đầu gồm 3 số nguyên dương M,N, Q ( 1 <= M,N <= 500; 1 <= Q <= 10 4 )
M dòng sau, mỗi dòng N số H ij là độ cao trung bình của block đất (i,j) ( 0 <= H ij <= 10 5 )
Q dòng sau, mỗi dòng 2 số L i , R i ( 0 <= L i <= R i <= 10 5 ).
Output
Gồm Q dòng, dòng thứ i gồm 1 số nguyên duy nhất là diện tích khu đất lớn nhất có thể trồng giống nho i. Nếu không tồn tại khu đất nào thỏa thì coi như diện tích bằng 0.
Example
Input: 4 5 3 34 33 25 21 13 35 35 33 21 16 50 45 33 33 16 93 83 66 51 23 22 90 33 35 20 100 Output: 9 4 16
- Người up: yenthanh132
- Nguồn bài: problem by winterwolf94