1158 : หาทำเลตั้งศูนย์บริการลูกค้า
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)

ร้านคอมพิวเตอร์ K.I.B. ต้องการขยายฐานลูกค้าไปยังเมืองใหม่ โดยเมืองดังกล่าวมีการวางผังเมืองเป็นพื้นที่สี่เหลี่ยมย่อยจำนวน MxN พื้นที่ (M แถว N หลัก) และจากการสำรวจสำมะโนประชากรทำให้ทราบจำนวนประชากรในแต่ละพื้นที่ (ดูภาพประกอบด้านล่าง)

เนื่องจากร้าน K.I.B. ต้องการเปิดศูนย์บริการลูกค้าเพียงร้านเดียวในเมืองนี้ ยิ่งไปกว่านั้นพื้นที่บริการที่ร้านให้บริการลูกค้าได้จะครอบคลุมบริเวณที่ประกอบด้วยสี่เหลี่ยมย่อยจำนวน KxK พื้นที่ (K แถว K หลัก) เท่านั้น ทางร้านจึงพยายามหาพื้นที่บริการที่ดีที่สุด ซึ่งในที่นี้หมายถึงพื้นที่บริการที่มีประชากรรวมกันมากที่สุด

5

9

2

9

1

2

8

9

1

6

9

1

3

9

8

4

2

1

5

7

2

7

9

3

8

5

2

7

6

8

1

6

2

1

7

7

1

9

4

1

8

5

2

3

9

8

5

6

3

3


ภาพประกอบตัวอย่างโจทย์ แสดงผลการหาทำเลตั้งศูนย์บริการลูกค้าในพื้นที่ขนาด 2x2  (K = 2) ของผังเมืองขนาด 5x10 ในที่นี้บริเวณที่ถูกเน้นคือพื้นที่บริการที่ดีที่สุด

จงเขียนโปรแกรมที่มีประสิทธิภาพในการหาจำนวนประชากรรวมในทำเลพื้นที่บริการที่ดีที่สุด


 

ข้อมูลนำเข้า

1.       บรรทัดแรกเป็นเลขจำนวนเต็มบวกสองตัวบอกจำนวนแถว (M) และจำนวนหลัก (N) ตามลำดับ โดยที่ 2 < M,N < 1000

2.       บรรทัดที่สองระบุขนาดพื้นที่บริการของร้าน (K) โดยที่ 0 < K < M และ 0 < K < N

3.       บรรทัดที่สามถึง M+2 ระบุจำนวนประชากรในแถวที่ 1 ถึง M ตามลำดับ ข้อมูลแต่ละบรรทัดประกอบด้วยตัวเลขจำนวนเต็มบวก N จำนวน ซึ่งระบุจำนวนประชากรของพื้นที่สี่เหลี่ยมย่อย
N หลัก เรียงจากซ้ายไปขวาในแถวนั้น ๆ แต่ละจำนวนถูกคั่นด้วยช่องว่าง โดยประชากรในแต่ละพื้นที่สี่เหลี่ยมย่อยมีจำนวนไม่เกิน 2,000 คน

ข้อมูลส่งออก

จำนวนประชากรภายในพื้นที่บริการที่ดีที่สุด

ที่มา : การแข่งขันคอมพิวเตอร์โอลิมปิกระดับชาติครั้งที่ 8 (SUTOI8)


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5 10
2
5 9 2 9 1 2 8 9 1 6
9 1 3 9 8 4 2 1 5 7
2 7 9 3 8 5 2 7 6 8
1 6 2 1 7 7 1 9 4 1
8 5 2 3 9 8 5 6 3 3
31
6 4
3
7 8 5 1
0 3 5 2
3 3 2 9
9 7 8 9
4 3 5 9
8 6 5 2
55

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 24 ผู้เยี่ยมชมและ 0 สมาชิก (2 บอท)