//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Sân golf

Sau nhiều lần tham gia kỳ thi Icamp và giành được nhiều giải thưởng, KAT quyết định đầu tư số tiền này để xây dựng một sân golf mang tên mình.

Sân golf mà KAT định xây nằm trong khuôn viên một khu đất hình chữ nhật kích thước M x N đã được chia thành lưới M hàng và N cột, các hàng được đánh số từ 1 đến M từ trên xuống dưới, các cột được đánh số từ 1 đến N từ trái sang phải. Ô đất tại hàng i, cột j có độ cao là Hij.

KAT sẽ chọn một hình chữ nhật con gồm các ô đất thuộc lưới để xây sân golf sao cho với hình chữ nhật con này thì các số trên 1 hàng bất kỳ tính từ trái sang phải, các số trên 1 cột bất kỳ tính từ trên xuống dưới đều có độ cao không giảm. Sau đó, KAT sẽ đặt lỗ golf tại góc trái trên và vị trí bắt đầu đánh tại góc phải dưới của hình chữ nhật để khi đánh, quả bóng luôn lăn xuống lỗ.

Bạn hãy giúp KAT chọn được sân golf có diện tích lớn nhất thỏa mãn yêu cầu trên.

InputGOLF.INP

  • Dòng đầu tiên ghi 2 số nguyên dương M và N là số hàng và số cột của khu đất.
  • Dòng thứ i trong số M dòng tiếp theo ghi N số nguyên Hi1, Hi2, .., HiN mà Hij là độ cao ô đất tại hàng i, cột j.

Output:            GOLF.OUT

  • Ghi ra 4 số nguyên P, Q, R, S với ý nghĩa hình chữ nhật con biểu diễn cho sân golf được chọn có góc trái trên là ô tại hàng P cột Q và góc phải dưới là ô tại hàng R cột S.

Giới hạn:

  • 1 ≤ M, N ≤ 1500
  • |Hij| ≤ 109
  • Thời gian: 2 s/test
  • Bộ nhớ: 32 MB
  • Có 40% số test có M, N ≤ 300

Ví dụ:

GOLF.INP GOLF.OUT
3 4

9 2 4 8

3 5 7 8

6 8 1 3

1 2 2 4

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: