1044 : Road Cut
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
คณะกรรมการผู้บริหารเมืองแห่งหนึ่งต้องการทำการตัดถนนผ่านพื้นที่ใจกลางเมือง โดยความต้องการของเมืองคือการตัดถนนเป็นเส้นตรงผ่านเมืองเป็นเส้นตรงทางทิศทางใดก็ได้ ระหว่างการตัดถนนผ่านทางด้านทิศตะวันตกไปยังด้านทิศตะวันออก (ซ้ายไปขวา) หรือทางด้านทิศเหนือไปยังด้านทิศใต้ (บนลงล่าง) ซึ่งพื้นที่ดังกล่าวมีมูลค่าของพื้นที่ในแต่ละส่วนไม่เท่ากัน นอกเหนือจากนั้นเมื่อตัดถนนแล้วจะทำให้พื้นที่ที่อยู่ติดถนนมีมูลค่าสูงขึ้น เพื่อให้การตัดถนนทำให้เกิดความเสียหายน้อยที่สุดและเพื่อประโยชน์ของเมืองโดยรวม การตัดถนนจึงควรตัดผ่านพื้นที่ที่มีมูลค่าต่ำที่สุดและยังทำให้มูลค่าพื้นที่โดยรวมของเมืองมีมูลค่าเพิ่มขึ้นสูงสุดอีกด้วย
โจทย์
จงเขียนโปรแกรมเพื่ออ่านข้อมูลนำเข้าของมูลค่าพื้นที่ย่อยภายในเมือง และการเปลี่ยนแปลงมูลค่าของพื้นที่ย่อยเมื่อมีการตัดถนนผ่าน ทั้งนี้กำหนดให้พื้นที่ภายในเมืองมีรูปทรงเป็นสี่เหลี่ยมผืนผ้าหรือสี่เหลี่ยมจัตุรัสเสมอ จากนั้นให้คำนวณหาเส้นทางที่ทำให้มูลค่าพื้นที่ของเมืองโดยรวมมีมูลค่าสูงที่สุดเพื่อให้คณะกรรมการนำไปพิจารณาทำการตัดถนน โดยกำหนดให้เส้นทางที่ถูกทำเป็นถนนจะมีมูลค่าพื้นที่เหลือ 0
ข้อมูลนำเข้า
บรรทัดแรกของข้อมูลนำเข้าเป็นจำนวนเต็มสองตัว n (2 < n <= 100) และ m (2 < m <= 100) ซึ่งเป็นขนาดของพื้นที่เมือง
ใน n บรรทัดถัดไป (เริ่มจากบรรทัดที่ 2 ถึงบรรทัดที่ n+1) เป็นข้อมูลของมูลค่าพื้นที่ย่อยจากเหนือลงใต้ โดยบรรทัดที่ i+1 จะแสดงข้อมูลของพื้นที่ย่อยในแถวที่ i (1 <= i <= n) โดยที่แต่ละบรรทัดจะมีตัวเลขทั้งหมด m ตัว (ตัวเลขแต่ละตัวจะถูกคั่นด้วยช่องว่าง) โดยตัวเลขแต่ละตัวในแต่ละบรรทัดเป็นจำนวนเต็มมีค่าระหว่าง 0 ถึง 100
ใน n บรรทัดถัดไป (เริ่มจากบรรทัดที่ n+2) เป็นข้อมูลการเปลี่ยนแปลงมูลค่าของพื้นที่ย่อยเมื่อมีถนนตัดผ่าน โดยบรรทัดที่ n+i+1 จะแสดงข้อมูลของการเปลี่ยนแปลงมูลค่าพื้นที่ย่อยในแถวที่ i (1 <= i <= n) โดยที่แต่ละบรรทัดจะมีตัวเลขทั้งหมด m ตัว (ตัวเลขแต่ละตัวจะถูกคั่นด้วยช่องว่าง) โดยตัวเลขแต่ละตัวในแต่ละบรรทัดเป็นจำนวนเต็มมีค่าระหว่าง 0 ถึง 20 (ซึ่งอาจจะทำให้มูลค่าของพื้นที่ย่อยมีค่าเกิน 100 ได้)
ข้อมูลส่งออก
มีทั้งหมด 1 บรรทัด มีตัวเลข 1 ตัวซึ่งแสดงถึงมูลค่ารวมของพื้นที่ภายในเมืองหลังจากทำการตัดถนนเรียบร้อยแล้ว
ที่มา: การแข่งขันคณิตศาสตร์ วิทยาศาสตร์ โอลิมปิกแห่งประเทศไทย สาขาวิชาคอมพิวเตอร์ ประจำปี 2550
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
โจทย์
จงเขียนโปรแกรมเพื่ออ่านข้อมูลนำเข้าของมูลค่าพื้นที่ย่อยภายในเมือง และการเปลี่ยนแปลงมูลค่าของพื้นที่ย่อยเมื่อมีการตัดถนนผ่าน ทั้งนี้กำหนดให้พื้นที่ภายในเมืองมีรูปทรงเป็นสี่เหลี่ยมผืนผ้าหรือสี่เหลี่ยมจัตุรัสเสมอ จากนั้นให้คำนวณหาเส้นทางที่ทำให้มูลค่าพื้นที่ของเมืองโดยรวมมีมูลค่าสูงที่สุดเพื่อให้คณะกรรมการนำไปพิจารณาทำการตัดถนน โดยกำหนดให้เส้นทางที่ถูกทำเป็นถนนจะมีมูลค่าพื้นที่เหลือ 0
ข้อมูลนำเข้า
บรรทัดแรกของข้อมูลนำเข้าเป็นจำนวนเต็มสองตัว n (2 < n <= 100) และ m (2 < m <= 100) ซึ่งเป็นขนาดของพื้นที่เมือง
ใน n บรรทัดถัดไป (เริ่มจากบรรทัดที่ 2 ถึงบรรทัดที่ n+1) เป็นข้อมูลของมูลค่าพื้นที่ย่อยจากเหนือลงใต้ โดยบรรทัดที่ i+1 จะแสดงข้อมูลของพื้นที่ย่อยในแถวที่ i (1 <= i <= n) โดยที่แต่ละบรรทัดจะมีตัวเลขทั้งหมด m ตัว (ตัวเลขแต่ละตัวจะถูกคั่นด้วยช่องว่าง) โดยตัวเลขแต่ละตัวในแต่ละบรรทัดเป็นจำนวนเต็มมีค่าระหว่าง 0 ถึง 100
ใน n บรรทัดถัดไป (เริ่มจากบรรทัดที่ n+2) เป็นข้อมูลการเปลี่ยนแปลงมูลค่าของพื้นที่ย่อยเมื่อมีถนนตัดผ่าน โดยบรรทัดที่ n+i+1 จะแสดงข้อมูลของการเปลี่ยนแปลงมูลค่าพื้นที่ย่อยในแถวที่ i (1 <= i <= n) โดยที่แต่ละบรรทัดจะมีตัวเลขทั้งหมด m ตัว (ตัวเลขแต่ละตัวจะถูกคั่นด้วยช่องว่าง) โดยตัวเลขแต่ละตัวในแต่ละบรรทัดเป็นจำนวนเต็มมีค่าระหว่าง 0 ถึง 20 (ซึ่งอาจจะทำให้มูลค่าของพื้นที่ย่อยมีค่าเกิน 100 ได้)
ข้อมูลส่งออก
มีทั้งหมด 1 บรรทัด มีตัวเลข 1 ตัวซึ่งแสดงถึงมูลค่ารวมของพื้นที่ภายในเมืองหลังจากทำการตัดถนนเรียบร้อยแล้ว
ที่มา: การแข่งขันคณิตศาสตร์ วิทยาศาสตร์ โอลิมปิกแห่งประเทศไทย สาขาวิชาคอมพิวเตอร์ ประจำปี 2550
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 5 4 2 3 2 1 4 5 8 4 2 5 3 2 1 4 0 2 2 1 8 1 1 2 3 2 2 2 2 1 2 1 1 2 1 2 1 0 1 1 1 0 | 62 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 21 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)