1123 : เหมืองแร่ (mine)
Problem type : Batch
Time limit : 2.0 second(s)
Memory limit : 64 megabyte(s)
Problem type : Batch
Time limit : 2.0 second(s)
Memory limit : 64 megabyte(s)
นอกจากประเทศแอฟริกาใต้จะเป็นเจ้าภาพจัดการแข่งขันฟุตบอลโลก 2010 แล้ว ยังเป็นประเทศที่อุดมสมบูรณ์ไปด้วยทรัพยากรธรรมชาติ เช่น ทองแดง เงิน และทองคำอีกด้วย คุณจึงวางแผนจะไปทำธุรกิจเปิดเหมืองทองแดง เหมืองเงิน และเหมืองทองคำที่ประเทศแอฟริกาใต้
พื้นที่ของประเทศแอฟริกาใต้มีลักษณะเป็นตารางสี่เหลี่ยมจัตุรัสขนาด N×N ช่อง แต่ละช่องจะมีทองแดง เงิน และทองคำอยู่ในปริมาณต่างๆ คุณต้องการสร้างเหมืองทองแดง เหมืองเงิน และเหมืองทองคำ ซึ่งแต่ละเหมืองจะเป็นสี่เหลี่ยมจัตุรัสขนาด K×K ช่อง ปริมาณแร่แต่ละชนิดที่คุณขุดได้จะมีค่าเท่ากับผลรวมของปริมาณแร่ชนิดนั้นในพื้นที่เหมืองของคุณ เหมืองแร่แต่ละเหมืองสามารถซ้อนทับกันได้โดยไม่มีผลกระทบต่อการขุดแร่
อย่างไรก็ตาม หากเหมืองแร่แต่ละเหมืองอยู่ห่างกันมากเกินไป จะทำให้การบริหารงานไม่สะดวก คุณจึงกำหนดเงื่อนไขว่า เหมืองแร่สองเหมืองใดๆ จะต้องมีพื้นที่ร่วมกันอย่างน้อยหนึ่งช่อง คุณต้องการเลือกตำแหน่งของเหมืองแร่แต่ละเหมืองให้เหมาะสม เพื่อให้ปริมาณแร่ที่ขุดได้ทั้งสามชนิดรวมกันมากที่สุดเท่าที่จะทำได้
งานของคุณ
จงเขียนโปรแกรมเพื่อรับปริมาณทองแดง เงิน และทองคำ ในพื้นที่แต่ละช่อง และคำนวณปริมาณรวมของแร่ทั้งสามชนิดที่มากที่สุดที่คุณสามารถขุดได้
ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N และ K (1 ≤ K ≤ N ≤ 1,000) แทนขนาดของพื้นที่ทั้งหมด และขนาดของเหมืองแร่แต่ละเหมือง
อีก N บรรทัดต่อมา ระบุจำนวนเต็มบวกบรรทัดละ N ตัว แทนปริมาณทองแดงในพื้นที่แต่ละช่อง
อีก N บรรทัดต่อมา ระบุจำนวนเต็มบวกบรรทัดละ N ตัว แทนปริมาณเงินในพื้นที่แต่ละช่อง
อีก N บรรทัดต่อมา ระบุจำนวนเต็มบวกบรรทัดละ N ตัว แทนปริมาณทองคำในพื้นที่แต่ละช่อง
ปริมาณของแร่แต่ละชนิดในพื้นที่แต่ละช่องจะมีค่าไม่เกิน 500
ข้อมูลส่งออก
มีบรรทัดเดียว แสดงปริมาณรวมของแร่ทั้งสามชนิดที่มากที่สุดที่คุณสามารถขุดได้
การให้คะแนน
30% ของข้อมูลทดสอบ จะมี N ≤ 15
50% ของข้อมูลทดสอบ จะมี N ≤ 50
ที่มา
การแข่งขัน IOI Thailand League เดือนมิถุนายน 2553
โจทย์โดย: สุธี เรืองวิเศษ
พื้นที่ของประเทศแอฟริกาใต้มีลักษณะเป็นตารางสี่เหลี่ยมจัตุรัสขนาด N×N ช่อง แต่ละช่องจะมีทองแดง เงิน และทองคำอยู่ในปริมาณต่างๆ คุณต้องการสร้างเหมืองทองแดง เหมืองเงิน และเหมืองทองคำ ซึ่งแต่ละเหมืองจะเป็นสี่เหลี่ยมจัตุรัสขนาด K×K ช่อง ปริมาณแร่แต่ละชนิดที่คุณขุดได้จะมีค่าเท่ากับผลรวมของปริมาณแร่ชนิดนั้นในพื้นที่เหมืองของคุณ เหมืองแร่แต่ละเหมืองสามารถซ้อนทับกันได้โดยไม่มีผลกระทบต่อการขุดแร่
อย่างไรก็ตาม หากเหมืองแร่แต่ละเหมืองอยู่ห่างกันมากเกินไป จะทำให้การบริหารงานไม่สะดวก คุณจึงกำหนดเงื่อนไขว่า เหมืองแร่สองเหมืองใดๆ จะต้องมีพื้นที่ร่วมกันอย่างน้อยหนึ่งช่อง คุณต้องการเลือกตำแหน่งของเหมืองแร่แต่ละเหมืองให้เหมาะสม เพื่อให้ปริมาณแร่ที่ขุดได้ทั้งสามชนิดรวมกันมากที่สุดเท่าที่จะทำได้
งานของคุณ
จงเขียนโปรแกรมเพื่อรับปริมาณทองแดง เงิน และทองคำ ในพื้นที่แต่ละช่อง และคำนวณปริมาณรวมของแร่ทั้งสามชนิดที่มากที่สุดที่คุณสามารถขุดได้
ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N และ K (1 ≤ K ≤ N ≤ 1,000) แทนขนาดของพื้นที่ทั้งหมด และขนาดของเหมืองแร่แต่ละเหมือง
อีก N บรรทัดต่อมา ระบุจำนวนเต็มบวกบรรทัดละ N ตัว แทนปริมาณทองแดงในพื้นที่แต่ละช่อง
อีก N บรรทัดต่อมา ระบุจำนวนเต็มบวกบรรทัดละ N ตัว แทนปริมาณเงินในพื้นที่แต่ละช่อง
อีก N บรรทัดต่อมา ระบุจำนวนเต็มบวกบรรทัดละ N ตัว แทนปริมาณทองคำในพื้นที่แต่ละช่อง
ปริมาณของแร่แต่ละชนิดในพื้นที่แต่ละช่องจะมีค่าไม่เกิน 500
ข้อมูลส่งออก
มีบรรทัดเดียว แสดงปริมาณรวมของแร่ทั้งสามชนิดที่มากที่สุดที่คุณสามารถขุดได้
การให้คะแนน
30% ของข้อมูลทดสอบ จะมี N ≤ 15
50% ของข้อมูลทดสอบ จะมี N ≤ 50
ที่มา
การแข่งขัน IOI Thailand League เดือนมิถุนายน 2553
โจทย์โดย: สุธี เรืองวิเศษ
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 3 2 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 | 84 |
| 4 2 7 7 1 1 7 7 1 1 1 1 1 1 1 1 1 1 1 8 8 1 1 8 8 1 1 1 1 1 1 1 1 1 1 1 1 1 9 9 1 1 9 9 1 1 1 1 1 1 | 96 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 23 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)