시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 295 | 48 | 35 | 17.327% |
재민이는 요리를 좋아한다. 그는 N일 동안 여러 조리법을 개발하려고 한다. 그가 조리법을 개발하는 방법은 다음과 같다.
이렇게 간단한 방법으로 조리법을 개발할 수 있는 그는 최대한 맛있는 요리들을 만들려고 한다.
시장에서는 매일 새로운 종류의 식재료가 판매된다. i번째 날 판매되는 식재료는 신선도 Fi를 가지고 있다. 만약 식재료를 사서 냉장고에 보관한다면 하루가 지날 때마다 신선도 Fi가 1씩 감소한다. 재민이는 냉장고에 식재료가 있다면 그 재료로 요리를 하기 전에는 또 식재료를 사지 않는다.
재민이는 i번째 날 Ci만큼의 요리실력을 가진다. 그의 요리실력은 꾸준히 증가하기 때문에 i < j인 i, j에 대해서 0 < Ci ≤ Cj를 만족한다. 만약 그가 신선도 F를 가진 식재료를 냉장고에서 꺼내 요리실력 C를 가지고 요리를 하면 F × C 만큼의 맛을 가진 요리가 만들어진다. 그가 요리할 때에는 친구 재현이를 초대하는데 재현이는 매우 위생적이어서 재민이의 냉장고에 있는 식재료가 Li 이상의 신선도를 가지고 있기를 바란다. 만약 냉장고에 있는 식재료가 그 기준을 만족하지 못한다면 재민이는 그날 요리할 수 없다. 재현이의 요구사항은 매일매일 바뀌어서 N 일 동안의 기준은 L1, L2, ..., LN으로 주어진다.
그는 새로운 요리를 만들고 나면 다음 날 바로 시장에 가서 식재료를 구매하고 또 다른 조리법을 생각한다. 재민이는 날마다 시장에 가서 식재료를 구매하거나, 요리를 하거나, 조리법을 고안하느라 아무것도 안 할 수도 있다 (식재료를 구매한 날 바로 요리를 하는 것도 가능하다). 재민이는 첫째 날에는 냉장고에 식재료가 없기 때문에 시장에 가서 식재료를 구매하고 N 번째 날에는 반드시 요리해서 냉장고를 비운다. 재민이가 만드는 요리들의 맛의 합의 최댓값을 구해보자. 만약 재현이의 까탈스런 요구사항 때문에 N 번째 날에 냉장고를 비울 수 없다면 "Impossible
" (따옴표 제외)을 출력한다.
입력은 4개의 줄로 이루어져 있다.
첫째 줄에는 N이 주어진다.
둘째 줄에는 공백으로 구분된 N개의 수 F1, F2, ..., FN이 공백으로 구분되어 주어진다.
셋째 줄에는 공백으로 구분된 N개의 수 C1, C2, ..., CN이 공백으로 구분되어 주어진다.
넷째 줄에는 공백으로 구분된 N개의 수 L1, L2, ..., LN이 공백으로 구분되어 주어진다.
재민이가 만드는 요리들의 맛의 합의 최댓값을 출력한다.
만약 N번째 날에 냉장고를 비울 수 없다면 "Impossible
"(따옴표 제외)을 출력한다.
이 서브태스크는 다음의 조건을 만족한다.:
이 서브태스크는 다음의 조건을 만족한다.:
이 서브태스크는 추가 제한 조건이 없다.
3 10 1 1 1 2 3 1 1 1
24
3 10 1 1 1 2 3 10 10 10
Impossible
10 3 4 1 5 9 2 6 5 3 5 10 11 12 13 14 15 16 17 18 19 1 4 1 4 2 1 3 5 6 2
526