시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 74 | 4 | 4 | 18.182% |
N students are sitting in a row, taking an exam. They are numbered from left to right with integers starting from 1. It is known how good each student’s work is: i-th student is going to score exactly Ai points.
Sometimes the proctor leaves for a break and when that happens students can cheat: any two or more consecutive students can gather and copy the best work among them. As a result, their scores become equal to the maximum score in that interval. Cheating can happen arbitrarily many (possibly zero) times.
In order to pass the exam i-th student needs to score exactly Bi points. Determine the maximum number of students that can pass the exam.
In the first line of the input there is an integer N.
In the next line there are N integers: A1, A2, ..., AN.
In the next line there are N integers: B1, B2, …, BN.
You should print exactly one integer: the maximum number of students.
번호 | 배점 | 제한 |
---|---|---|
1 | 14 | N ≤ 10 |
2 | 12 | N ≤ 105, All elements of B are equal (B1 = B2 = ⋯ = Bn) |
3 | 13 | N ≤ 5000, A is strictly increasing (A1 < A2 < ⋯ < An) |
4 | 23 | N ≤ 105, All elements of A are distinct |
5 | 16 | N ≤ 200 |
6 | 22 | N ≤ 5000 |
3 1 2 3 2 2 2
2
4 10 1 9 1 10 9 10 9
3
In the first example the first two students can cheat after which the scores becomes 2,2,3 and they both pass the exam.
In the second example students 2 and 3 can pass the exam but not both at the same time. Note that this test can’t be present in subtasks 2,3 or 4.