아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

구현상의 불규칙성

시간 제한1초메모리 제한1024 MB

요약
해결한 각 문제에 필요한 컴퓨터 시간과 대회 중 해당 문제를 해결한 시각이 주어질 때, 팀이 사용했을 수 있는 컴퓨터의 최소 대수를 구한다.
난이도

보통10점 중 7점

유형
그리디, 정렬, 이분 탐색, 구간
정답자
아직 제출이 없습니다

문제

최근 BAPC 예선에서 상위 팀들의 성적에 감명을 받은 당신은, 팀들이 문제를 구현할 때 컴퓨터를 한 대만 사용할 수 있는지 여러 대를 사용할 수 있는지 궁금해졌다.

조직에 불필요하게 질문을 더 하러 가지 않고, 당신은 이 문제를 직접 알아내기로 한다. 심사위원이므로, 당신은 각 문제를 푸는 데 필요한 컴퓨터 시간의 추정치를 이미 알고 있다.

이 정보와, 상위 팀이 푼 각 문제를 대회 중 몇 시각에 풀었는지를 이용하여, 그 팀이 사용한 컴퓨터 수의 최솟값을 구하라.

팀은 한 문제도 통과하기 전에 여러 문제를 동시에 작업할 수 있다. 또한, 참가자들은 멀티태스킹을 잘하여 한 문제를 여러 대의 컴퓨터로 동시에 작업할 수 있지만, 각 컴퓨터는 한 번에 한 문제에만 사용할 수 있다.

입력

입력은 다음과 같다.

  • 정수 nn (1≤n≤1051\leq n\leq 10^5)이 주어지는 한 줄. nn은 대회의 문제 수이다.
  • nn개의 정수 t_1,t_2,…,t_nt\_1, t\_2, \dots, t\_n (1≤t_i≤1041\leq t\_i \leq 10^4)이 주어지는 한 줄. t_it\_i는 문제 ii를 푸는 데 필요한 컴퓨터 시간이다.
  • nn개의 정수 s_1,s_2,…,s_ns\_1, s\_2, \dots, s\_n (1≤s_i≤1091\leq s\_i \leq 10^9 또는 s_i=−1s\_i = -1)이 주어지는 한 줄. s_is\_i는 문제 ii를 푼 시각이며, 풀지 않았다면 −1-1이다.

팀이 적어도 한 문제는 풀었음이 보장된다.

출력

팀이 사용한 컴퓨터 수의 최솟값을 출력하라.

예제4

  1. 예제 1

    입력
    11
    50 8 10 6 300 5 6 3 18 5 12
    117 23 63 6 -1 48 80 42 37 13 131
    
    예상 출력
    1
    
  2. 예제 2

    입력
    1
    10
    3
    
    예상 출력
    4
    
  3. 예제 3

    입력
    2
    2 4
    3 3
    
    예상 출력
    2
    
  4. 예제 4

    입력
    2
    4 6
    10 10
    
    예상 출력
    1