NPSC 國是一個得天獨厚的國家，國內盛產金礦以及銀礦，因此吸引了大量的遊客前往， 大家都希望能在這裡挖到寶藏，一夜致富，這其中當然包含了厭
倦了整天背單字的小 B 。 具體來說，NPSC 國可以被表示成一個二維平面，且總共有 n 個金礦以及 m 個銀礦。金礦以及銀礦都有各自的位置以及價
值，第 i 個寶藏位於 (x,y) 的位置，且價值為 v 。小 B 挖礦的方式十分特別：他會選擇兩個任意的寶藏（不管是金礦還是銀礦，且注意這兩個寶藏可以是
同一個，此時視為小 b 只拿走一個），並將在「以這兩個寶藏為對角線的矩形」內(含邊界)的所有寶藏都搜刮到。注意到，一旦選擇了對角線上的兩個寶
藏，小 B不能跳過任何一個在該矩形當中的寶藏！ 當然小 B 也不能隨意挖礦。由於他最後還是得坐飛機把他挖到的寶藏帶回家，為了不超過飛機托運的重
量限制，小 B 最多只能帶走 k 個金礦（銀礦的重量相較於金礦可以忽略）。小 B 就要出發了，請你幫忙估算一下他最多能挖到總價值為多少的寶藏。
輸入第一行有三個整數 n, m, k ，分別代表金礦的數量、銀礦的數量，以及小 B 最多能擁有的金礦數量。 接著 n + m 行，每行有三個正整數。其中
第 i 行為 x , y , v ，代表第 i 個寶藏的位置以及價值。第 1 個到第 n 個為金礦，第 n + 1 個到第 n + m 個為銀礦。
1. 0 ≤ k ≤ n
2. 保證同一個位置至多只有一個寶藏
輸出一個整數代表小 B 最多能挖到總價值為多少的寶藏。
2 2 2 1 1 1 2 2 10 1 2 100 2 1 1
112
公開 測資點#0 (5%): 0.5s , <1M
公開 測資點#1 (10%): 4.0s , <1M
公開 測資點#2 (5%): 0.5s , <1M
公開 測資點#3 (5%): 0.5s , <1M
公開 測資點#4 (5%): 0.5s , <1M
公開 測資點#5 (5%): 0.2s , <1K
公開 測資點#6 (5%): 0.2s , <1K
公開 測資點#7 (10%): 4.0s , <1M
公開 測資點#8 (10%): 4.0s , <1M
公開 測資點#9 (10%): 4.0s , <1M
公開 測資點#10 (10%): 4.0s , <1M
公開 測資點#11 (10%): 4.0s , <1M
公開 測資點#12 (10%): 4.0s , <1M
dp, suffix/prefix method, discretion (CF 2000)
10% 測資滿足 1 ≤ n+m ≤ 100 , 1 ≤ x,y,v ≤ 103
30% 測資滿足 1 ≤ n+m ≤ 500 , 1 ≤ x,y,v ≤ 103
100% 測資滿足 1 ≤ n+m ≤ 5000 , 1 ≤ x,y,v ≤ 109
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||