TopCoder

Thumb mikazuki.munechika.full.1936339
FHVirus
$\fbox{背包問題} 比 \definecolor{p}{RGB}{219,48,122}{\color{p}\fbox{FFT}} 難 QWQ$

User's AC Ratio

91.2% (52/57)

Submission's AC Ratio

51.5% (70/136)

Tags

Description

小蚯蚓是一個旅行家,他到了一個稱作Linear City的地方。

這個城市共有n棟建築。所有建築物都是高樓大廈,每棟都有高度Hi跟美觀度Bi。

依序排成一條直線,從左到右編號為1~n。

小蚯蚓想要選一個景觀很好的地方慢慢欣賞風景(也就是那些建築物)。

但是,小蚯蚓有閃光(一種眼疾,會看東西看得很不清楚),頂多只能看到距離k以內的建築物。

而且建築物也可能會被其他建築物擋住。

也就是一棟建築物會被看到的充要條件就是:

 1.該建築物跟小蚯蚓的距離要在k以內
 2.該建築物到小蚯蚓之間任何建築物都只能比該建築物低(相等也是看不到的喔!)

他發明了一個函式可以估計該點的風景美觀度,也就是View(p) 其中1<=p<=n。

所謂View(p)就是,站在建築物p的右邊往左看。所有看得到的建築物的美觀度加起來。

例如下圖就是在n=9, k=4下計算得View(6)=4

現在小蚯蚓想問你他站在哪裡才能得到最大的View()值?

Input Format

第一行有兩個數字n, k表示這個城市的建築數目以及小蚯蚓的視力範圍。

第二行有n個數字,第i個數字Hi表示建築物i的高度,

第三行有n個數字,第i個數字Bi表示建築物i的美觀度。

1 <= n <= 500,000;
1 <= k <= n;
1 <= Hi<= 1,000,000,000
-1000 <= Bi <= 1000

Output Format

輸出在同一行內包含兩個數字p q,以空白分開。

表示站在p的位置時View(p)=q 有風景美觀度的最大值。

若有很多個p的View()相同,輸出最小的那個。

Sample Input

9 4
8 6 3 7 3 5 4 3 8
5 -4 2 -3 2 7 -1 -4 6

Sample Output

9 6

Hints

很久以前一直以為散光寫作閃光...

對了,範測就是那張圖。

這題用cin絕對會超時

Problem Source

原TIOJ1618 / Problem Setter:ATP

Subtasks

No. Testdata Range Score
1 0 16
2 1 16
3 2 16
4 3 16
5 4 16
6 5 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2500 65536 262144 1
1 2500 65536 262144 2
2 2500 65536 262144 3
3 2500 65536 262144 4
4 2500 65536 262144 5
5 2500 65536 262144 6