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.|

GRAPE - Trồng nho

            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ố Li và Ri chỉ có thể được trồng trên các block đất có độ cao trung bình trong đoạn [Li,Ri]. 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 <= 104)
            M dòng sau, mỗi dòng N số Hij là độ cao trung bình của block đất (i,j)  ( 0 <= Hij<= 105)
            Q dòng sau, mỗi dòng 2 số Li, Ri ( 0 <= Li<= Ri<= 105).

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

Được gửi lên bởi:Hacker7
Ngày:2012-12-27
Thời gian chạy:0.200s-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:problem by winterwolf94

hide comments
2016-08-22 10:18:09


Last edit: 2016-08-22 12:14:31
2015-10-18 16:05:42
lại 1 bài time chặt bựa chả được cái ích lợi gì , web để ôn thi quốc gia chủ yếu 1 s mà cứ để time kiểu này thì...
2013-06-11 13:27:30 vn_army
mình nghĩ chạy nhanh,chậm hơn nhau 0,xx giây chẳng thành vấn đề j cả, nên để giới hạn với time thoải mái đủ để thuật toán ổn ổn là qua, cố bắt nhau vài cái trick làm j , máy tính bây giờ chạy O(10^6) với O(10^7) thì nó cũng khác j nhau đâu ...
2013-03-29 03:11:00 anh chỉ yêu mình em....ÐKH......
Quan điểm chủ quan của mình PS siết time quá chặt khi mà cho time cái kiểu 0.2s-1s. Bài này mình biết các bạn lấy từ đề ACM Latin America 2009, và đã tự thử chấm bài trên livearchive, thấy chạy rất bình thường và accept. Mình cũng chẳng hiểu siết nhau 1 cái log thì giải quyết đc vấn đề gì?

//Update:
Bổ sung thêm là mình nghĩ các bạn nên học tập các PS của TopCoder hay là Codeforces ấy. TopCoder thường để giới hạn có N=50 thôi. Còn Codeforces để giới hạn thời gian rất hợp lý, mình chưa bao giờ thấy ai phàn nàn là time siết chặt cả.

Last edit: 2013-03-29 03:15:47
2013-01-07 01:04:50 True Love
PS xem dùng mình bài 8422188 bị tle hay wa vậy. cám ơn.
2013-01-06 00:23:59 Thắng 20 cm
đề bài nói độ cao trung bình trong đoạn [Li,Ri] làm mình tưởng tính trung bình cộng các độ cao @_@
2012-12-28 15:04:14 Noyethug
à đó là do sơ suất khi cài đặt của em thôi ạ! Nhưng mà mặc định nó =0 nên khi đọc lại coi sai ở đâu em vẫn nghĩ là nó không ảnh hưởng đến kq nếu l>0 :p
p/s: anh muốn chặn times chắc phải để 0.100s :P có khi vẫn chưa chặn được @@ k thì để 1s sang máy cũ =))

Last edit: 2012-12-28 15:07:05
2012-12-28 14:37:13 LoneWolf
ah đúng thật :| Li>=0, sry các bạn vì sai sót nhỏ này :D.
tuy nhiên bạn đặt cận ngay biên cũng hơi nguy hiểm. mình luôn để cận trong vùng chứa giá trị của mảng :)
2012-12-28 13:31:02 Noyethug
đúng rồi ạ! Vì bài em sub ở hôm thi chỉ sai khi test có số âm hoặc 0, em có so sánh a[i,j]>=l vs số j>N nhưng mặc định nó sẽ là 0 nên em nghĩ a[i,j]>=L vs j>n không xảy ra. Nhưng nó lại xảy ra khiến bài em mất mấy test hôm thi
2012-12-28 12:52:52 Think like Nguyễn Mai Lan
PS xem lại Li vs Ri trong file input có đúng giới hạn ko. Hình như là có 0 và số âm :|
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.