시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 94 | 15 | 15 | 23.438% |
경기북과학고등학교에서는 물리, 정보, 수학 총 3과목에 대해서만 시험을 본다. 이제 곧 학교를 졸업하는 래오는 학교 생활 동안 치른 $N$번의 시험을 바탕으로 포트폴리오를 작성하려 한다. 래오는 자신의 성적이 너무 낮아 보이는 것도, 높아 보이는 것도 원하지 않기 때문에 세 과목의 성적 중 중앙값을 순서대로 포트폴리오에 적을 것이다.
또한 래오는 포트폴리오에 적힌 성적이 점점 증가하는 것을 원한다. 성적이 같은 경우는 허용되지 않으며, 반드시 증가해야 한다. 아쉽게도 래오의 현재 성적표로는 이를 만족하지 못할 수 있기 때문에 래오는 친구 지훈이의 힘을 빌려 목표를 이루려 한다. 지훈이는 각 시험당 최대 한 과목의 점수를 원하는 점수로 바꾸어줄 수 있다. 경기북과학고등학교의 시험 점수는 항상 음이 아닌 정수이기 때문에, 바뀐 점수 역시 음이 아닌 정수여야 한다.
하지만 또 아쉽게도, 이조차 항상 가능하지 않다는 것을 알게 되었다. 대신 포트폴리오의 최장 증가 부분 수열(Longest Increasing Subsequence, LIS) 길이를 최대화하려 한다. 지훈이의 도움을 적절히 받아 만들 수 있는 포트폴리오의 최장 증가 부분 수열 길이의 최댓값을 구하여라.
첫 번째 줄에 시험의 개수 $N$이 주어진다. $(1 \leq N \leq 200\,000)$
두 번째 줄에 각 시험에서의 물리 점수 $A_1, A_2, \cdots, A_N$이 순서대로 공백으로 구분되어 주어진다. $(0 \leq A_i \leq 2 \times 10^9)$
세 번째 줄에 각 시험에서의 정보 점수 $B_1, B_2, \cdots, B_N$이 순서대로 공백으로 구분되어 주어진다. $(0 \leq B_i \leq 2 \times 10^9)$
네 번째 줄에 각 시험에서의 수학 점수 $C_1, C_2, \cdots, C_N$이 순서대로 공백으로 구분되어 주어진다. $(0 \leq C_i \leq 2 \times 10^9)$
시험 점수는 모두 정수이다.
포트폴리오에서 만들 수 있는 최장 증가 부분 수열 길이의 최댓값을 출력한다.
3 1 2 3 0 4 3 5 3 3
3
4 1 2 3 2 0 3 3 2 4 3 5 3
3
2 1 0 0 0 1 0
1