정말 간단한 문제

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

요약
두 양의 정수 수열이 주어질 때 연속 부분 구간의 y 합 대 x 합 비율의 최댓값과 그 비율을 이루는 가장 긴 구간 길이를 기약분수로 구하여 출력한다.
난이도

어려움10점 중 9점

유형
이분 탐색, 수학, 누적 합, 분할 정복
정답자
아직 제출이 없습니다

문제

수열 x_ix\_i와 y_iy\_i가 주어진다. 아래 간단한 질문에 답을 해보자.

  • x_ix\_i, y_iy\_i의 ll번째 원소부터 rr번째 원소까지의 합의 비 ∑_i=lry_i∑_i=lrx_i\frac{\sum\_{i = l}^{r} y\_i}{\sum\_{i = l}^{r} x\_i}가 최대가 될 때의 값과 그때의 구간 길이의 최댓값을 구하라.

입력

첫 번째 줄에 수열의 길이 nn이 주어진다. (1≤n≤500,0001 \leq n \leq 500 \\, 000)

두 번째 줄에 수열 x_ix\_i의 원소 nn개가 공백으로 구분되어 주어진다. (1≤x_i≤1091 \leq x\_i \leq 10^9)

세 번째 줄에 수열 y_iy\_i의 원소 nn개가 공백으로 구분되어 주어진다. (1≤y_i≤1091 \leq y\_i \leq 10^9)

입력으로 들어오는 값은 모두 정수이다.

출력

첫 번째 줄에 비의 최댓값을 출력한다. 기약분수로 나타냈을 때 AB\frac{A}{B}라면 AA와 BB를 공백으로 구분하여 출력한다.

두 번째 줄에 비가 최대가 될 때의 구간 길이의 최댓값을 출력한다.

힌트

계산 과정에 필요한 수의 값이 32비트 정수 범위를 넘을 수 있음을 유의하라.

예제1

  1. 예제 1

    입력
    5
    4 1 2 3 2
    6 1 3 4 3
    
    예상 출력
    3 2
    1