TopCoder

User's AC Ratio

95.0% (19/20)

Submission's AC Ratio

47.0% (31/66)

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

For Testdata: 0 ~ 0, Score: 16
For Testdata: 1 ~ 1, Score: 16
For Testdata: 2 ~ 2, Score: 16
For Testdata: 3 ~ 3, Score: 16
For Testdata: 4 ~ 4, Score: 16
For Testdata: 5 ~ 5, Score: 20
No. Time Limit (ms) Memory Limit (KiB)
0 2500 65536
1 2500 65536
2 2500 65536
3 2500 65536
4 2500 65536
5 2500 65536