루미 알고리즘

#1586다이아Upplega

PO 2024 훈련 캠프코딩출제 Harry Zhang영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

“It's beginning to look a lot like Christmas Everywhere you go”

It is only truly winter once the snow has settled on all the branches of the N trees on the street outside your house. The street with all the trees can be represented in an arbitrarily large grid. Along the street, the N trees stand in a row. The trunk of each tree i is located at position pos_i and is described by a rectangle with a width of 1, occupying the entire column pos_i. Additionally, each tree i has s_i branches. Each branch is described by a rectangle with a height of 1 that sticks out from the trunk and is an integer number of units wide. It is guaranteed that the squares that each branch occupies do not contain any other branch or trunk. It is also guaranteed that no branch goes beyond another tree, not even above it.

After a snowy evening, Upplega has settled on all the trees. Upplega is the Swedish term for snow that has accumulated on top of a tree's branches. On each unit length of each branch, there is 1 unit of snow. The snow is so small that it does not occupy a square. In other words, the height is negligible.

You are a true winter enthusiast who loves Christmas songs, the cozy cold weather, and above all, all the Upplega. According to the weather forecast, there will soon be a big storm that will shake all the trees quite vigorously. When a tree is shaken, the snow on its branches will start falling straight down until the snow either safely lands on a branch belonging to a tree that is not shaking, or lands on the ground.

Despite the storm approaching, you have time to protect K trees from shaking by rooting them. Since you love snow so much, you want to calculate the maximum number of snow units you can prevent from falling to the ground by rooting exactly K trees.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: The picture shows sample 1.

Input

The first row of input contains two integer N and K (1 ≤ K ≤ N ≤ 10^5), the number of trees on the street and the number trees you have time to protect from being shaken.

The second row contains N integers pos_1, pos_2, …, pos_N (0 ≤ pos_i ≤ 10^9), where pos_i is the number of length units from the start of the street to tree i. The trees will be given in sorted order and it is guaranteed that no two trees occupy the same position. Formally, this means that for all i<j, it holds that pos_i < pos_j.

The third line contains N integers s_1, s_2, …, s_N (1 ≤ s_i ≤ 10), where s_i is the number of branches on tree i.

Finally, 2N rows follows, with 2 rows per tree, which describes its branches:

  • The first row contains s_i integers h_{i,1}, h_{i,2}, …, h_{i,s_i} (1 ≤ h_{i,j} ≤ 10^9), where h_{i,j} is the height of the j:th branch belonging to tree i.
  • The second row contains s_i integers l_{i,1}, l_{i,2}, …, l_{i,s_i} (-10^9 ≤ l_{i,j} ≤ 10^9 , l_{i,j} ≠ 0). Each l_{i,j} describes the length and direction of the j:th branch of tree i. If l_{i,j} is positive, it means that branch j is directed to the right and is l_{i,j} length units long. If l_{i,j} is negative, the branch is directed to the left and is |l_{i,j}| length units long.

No branch will be outside the beginning of the street located at 0, or beyond 10^9 length units from the beginning of the street.

Output

Print the maximum number of snow units that you can prevent from falling to the ground by rooting exactly K trees.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPoint valueConstraints
15All branches are directed to the right. Formally, l_{i,j} > 0 holds for all i,j.
25K = 1
37N ≤ 15
411N ≤ 2000, ∣l_{i,j}∣ ≤ 2 · 10^5, pos_i ≤ 2 · 10^5 for all i,j.
523N ≤ 2000
631∣l_{i,j}∣ ≤ 2 · 10^5, pos_i ≤ 2 · 10^5 for all i,j.
718No additional constraints.

Group 4 and 6 additionally guarantee that all trees and branches have positions in the interval between position 0 and position 4 · 10^5.

Explanation of sample 1:

By choosing to save the first and second tree, we prevent 10 snow units from falling from tree 1, 18 from tree 2 and 9 from tree 3, totalling 10+18+9=37.

예제

예제 1

입력
3 2
5 11 21
4 4 3
3 3 5 5
-3 3 -2 2
3 6 7 8
8 -2 4 -4
6 7 8
-7 5 -4
출력
37

예제 2

입력
1 1
1000
4
10 5 8 6
2 3 -4 -5
출력
14

예제 3

입력
2 2
1 2
1 2
1
-1
1 2
1 2
출력
4

출처 표기

출처: Programmeringsolympiaden 2024년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.