루미 알고리즘

#1601골드The Duckamyds

PO 2025 결선코딩출제 Theodor Beskow영어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Kalle has just received a large box of colorful rubber ducks as a gift. After counting them carefully, he knows exactly how many ducks he has of each color. Now, he wants to build the world's largest duck pyramid!

To build the pyramid, Kalle has borrowed a special pyramid construction stand whose height allows him to build a pyramid with up to M layers of ducks. A duck pyramid is built in layers, where the bottom layer is layer 1, the next is layer 2, and so on. To make the pyramid look nice, Kalle has decided that each layer should consist of ducks of the same color. He has also decided which color each layer should have.

If the pyramid has height H, then layer i must contain exactly (H-i+1)^2 ducks. For example, in a pyramid with height 3:

  • Layer 1 (bottom) needs 3^2 = 9 ducks.
  • Layer 2 (middle) needs 2^2 = 4 ducks.
  • Layer 3 (top) needs 1^2 = 1 duck.

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

Figure 1: Harry's reaction when he sees a duck pyramid where layer 1 consists of 9 yellow ducks, layer 2 consists of 4 blue ducks, and layer 3 consists of 1 green duck.

Help Kalle calculate how tall the pyramid can be! Note that the height H cannot exceed M.

Input

On the first line, there are two integers N and M (1 ≤ N, M ≤ 10^5), the number of different colors and the number of layers in the pyramid.

On the second line, there are N integers a_1, a_2, ..., a_N (0 ≤ a_j ≤ 10^18), where a_j indicates the number of ducks of color j.

On the third line, there are M integers c_1, c_2, ..., c_M (1 ≤ c_i ≤ N), where c_i indicates which color should be used in layer i.

Note that even though Kalle has decided which colors all layers should have, he may build a pyramid that does not use all M layers.

Output

Print an integer: the maximum height H the pyramid can have.

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.

GroupPointsConstraints
111N = 1
219c_i = i, for all 1 ≤ i ≤ M.
317∑ a_k ≤ 10^5
419N, M ≤ 2000
534No additional constraints.

Explanation of Samples

In the first example, Kalle only has ducks of one color, and he has 17 of them. The pyramid stand allows up to 5 layers. To build a pyramid of height 3, the following ducks are needed:

  • 9 ducks in layer 1
  • 4 ducks in layer 2
  • 1 duck in layer 3

A total of 14 ducks are used. It is not possible to build a pyramid with height 4, because that would require 4^2 + 3^2 + 2^2 + 1^2 = 30 ducks, which is more than the 17 ducks available.

In the second example, Kalle has:

  • 2 ducks of color 1
  • 19 ducks of color 2
  • 12 ducks of color 3

The color order in the layers is: 2, 3, 2, 1, 2. A pyramid of height 3 can be built by using:

  • 9 ducks of color 2 in layer 1
  • 4 ducks of color 3 in layer 2
  • 1 duck of color 2 in layer 3

This uses 10 ducks of color 2 and 4 ducks of color 3, which is within the available limits. A taller pyramid is not possible with the given restrictions.

예제

예제 1

입력
1 5
17
1 1 1 1 1
출력
3

예제 2

입력
3 5
2 19 12
2 3 2 1 2
출력
3

예제 3

입력
2 3
4 2
1 2 1
출력
2

출처 표기

출처: Programmeringsolympiaden 2025년 결선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.