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

MINCUT - VOI 2015 Day 2 - Cắt hình

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mincut


Cho A là lưới ô vuông gồm m dòng và n cột. Các dòng của lưới được đánh số từ 1 đến m, từ trên xuống dưới. Các cột của lưới được đánh số từ 1 đến n, từ trái sang phải. Ô nằm trên giao của dòng i và cột j của lưới, được gọi là ô (ij), chứa số nguyên không âm ai,j có giá trị không vượt quá 106.

Các lưới ô vuông như vậy luôn là đối tượng cho nhiều nghiên cứu thú vị. Vừa qua, trong giờ học ôn luyện cho kỳ thi học sinh giỏi Tin học, Hùng được cô giáo giao cho giải quyết bài toán trả lời truy vấn sau đây đối với bảng đã cho:

Cho một hình chữ nhật con có ô trái trên là ô (x,y) và ô phải dưới là ô (u,v), cần đưa ra chênh lệch nhỏ nhất trong số các chênh lệch giữa hai tổng các số trong hai hình chữ nhật thu được bằng việc cắt ngang hoặc cắt dọc hình chữ nhật đã cho dọc theo đường kẻ của lưới. Giả thiết (x,y) và (u,v) là hai ô khác nhau trên lưới.

Bạn hãy giúp Hùng giải quyết bài toán đặt ra.

Yêu cầu: Cho lưới A k bộ xq, yq , uqvq (q = 1, 2, ..., k) tương ứng với k truy vấn, hãy đưa ra các câu trả lời cho k truy vấn.

Dữ liệu vào: 

  • Dòng đầu tiên chứa ba số nguyên m, n, k (k m×n);
  • m dòng tiếp theo, dòng thứ i chứa n số nguyên không âm ai1, ai2, ..., ain;
  • Dòng thứ q trong số k dòng tiếp theo chứa 4 số nguyên xq, yq, uq, vq (q = 1, 2, ..., k).

Dữ liệu ra:

  • Ghi ra file văn bản MINCUT.OUT gồm k dòng, mỗi dòng chứa một số là câu trả lời cho một truy vấn theo thứ tự xuất hiện trong file dữ liệu vào.

Ràng buộc:

  • Có 30% số test ứng với 30% số điểm của bài có m, n ≤ 10.
  • Có 30% số test khác ứng với 30% số điểm của bài có  m, n ≤ 100.
  • Có 40% số test  ứng với 40% số điểm còn lại của bài có m, n ≤ 1000.

 

Ví dụ:

Input:

3

3

2


1

1

1


1

1

1


1

1

1


1

1

3

3

1

1

3

2

Output:

3

 

0

 
 
 
 
 

Được gửi lên bởi:VOJ Team
Ngày:2015-01-13
Thời gian chạy:2s
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 JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:VOI15 day 2

hide comments
2016-04-11 14:56:45 Nguyen Cuong


Last edit: 2016-04-11 14:59:57
2016-02-20 09:15:35 Nguyễn Thành Nhân
chặt chặt chặt
2016-01-02 19:01:17 --QDTB---
m.n chú ý để hết là int64 nha
2015-12-12 10:35:07
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/12/12/voi-2015-day-2-cat-hinh-mincut/

Last edit: 2015-12-12 10:35:18
2015-12-12 09:44:08
Tên file thêm tào lao làm mất 1 đấm AC
2015-12-02 05:12:35 thantung


Last edit: 2015-12-02 08:53:17
2015-11-30 15:43:14
minh lam khoang 11 giay moi AC
2015-11-15 16:11:01 White Shadow
1 đấm :)
2015-11-15 02:54:30
mọi người tham khảo này: http://www.oni.vn/woGFF
2015-09-24 19:05:36 Nguyễn Vĩnh Thịnh


Last edit: 2015-11-30 08:29:02
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.