24475번 - Self Study 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 265 | 84 | 77 | 31.429% |
문제
In the third semester of the first grade of JOI High School, $N$ courses are given for $M$ weeks from the first week to the $M$-th week. The courses are numbered from $1$ to $N$. In each week, $N$ classes are given. The $i$-th class in each week is a class for Course $i$.
Bitaro is a student of the first grade. In each of the $N \times M$ classes, he takes one of the following actions.
- Action 1: Bitaro attends the class. If he attends a class for Course $i$ ($1 ≤ i ≤ N$), the comprehension level of Course $i$ will be increased by $A_i$.
- Action 2: Bitaro does not attend the class. Instead, he chooses any one of the courses, and studies for the chosen course by himself. If he studies for Course $i$ ($1 ≤ i ≤ N$) by himself for the duration of a class, the comprehension level of Course $i$ will be increased by $B_i$.
In the beginning, the comprehension level of every course is $0$. Since Bitaro wants to practice competitive programming after school, he will not study outside the duration of the classes. When all the classes in the third semester finish, the final examination will be held.
Bitaro does not want to get a failing grade. Therefore, he wants to maximize the minimum comprehension level of the courses at the moment of the final examination.
Given the length of the semester, the number of the courses, and the incremental values of the comprehension levels, write a program which calculates the maximum possible value of the minimum comprehension level of the courses at the moment of the final examination.
입력
Read the following data from the standard input. Given values are all integers.
$\begin{align*} & N\,M \\ & A_1 \, A_2 \, \cdots \, A_N \\ & B_1 \, B_2 \, \cdots \, B_N\end{align*}$
출력
Write one line to the standard output. The output should contain the maximum possible value of the minimum comprehension level of the courses at the moment of the final examination.
제한
- $1 ≤ N ≤ 300\,000$.
- $1 ≤ M ≤ 1\,000\,000\,000$.
- $1 ≤ A_i ≤ 1\,000\,000\,000$ ($1 ≤ i ≤ N$).
- $1 ≤ B_i ≤ 1\,000\,000\,000$ ($1 ≤ i ≤ N$).
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $M = 1$. |
| 2 | 25 | $N \times M ≤ 300\,000$, $A_i = B_i$ ($1 ≤ i ≤ N$). |
| 3 | 27 | $N \times M ≤ 300\,000$. |
| 4 | 29 | $A_i = B_i$ ($1 ≤ i ≤ N$). |
| 5 | 9 | No additional constraints. |
예제 입력 1
3 3 19 4 5 2 6 2
예제 출력 1
18
For example, if Bitaro studies in the following way, the compehension level of Course $1$, $2$, $3$ will be $19$, $18$, $19$, respectively.
- In the first week, at the time of Course $1$, he studies for Course $2$ by himself.
- In the first week, at the time of Course $2$, he studies for Course $2$ by himself.
- In the first week, at the time of Course $3$, he attends the class for Course $3$.
- In the second week, at the time of Course $1$, he attends the class for Course $1$.
- In the second week, at the time of Course $2$, he studies for Course $3$ by himself.
- In the second week, at the time of Course $3$, he attends the class for Course $3$.
- In the third week, at the time of Course $1$, he studies for Course $3$ by himself.
- In the third week, at the time of Course $2$, he studies for Course $2$ by himself.
- In the third week, at the time of Course $3$, he attends the class for Course $3$.
Since the minimum comprehension level of the courses cannot be larger than or equal to $19$, output $18$. This sample input satisfies the constraints of Subtasks 3, 5.
예제 입력 2
2 1 9 7 2 6
예제 출력 2
7
This sample input satisfies the constraints of Subtasks 1, 3, 5.
예제 입력 3
5 60000 630510219 369411957 874325200 990002527 567203997 438920902 634940661 593780254 315929832 420627496
예제 출력 3
41397427274960
This sample input satisfies the constraints of Subtasks 3, 5.
예제 입력 4
4 25 1 2 3 4 1 2 3 4
예제 출력 4
48
This sample input satisfies the constraints of Subtasks 2, 3, 4, 5.
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호