페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3957

부분수열의 합은 7 2s 512MB

문제

Farmer John의 소 N마리가 줄을 서 있다. 각 소에는 서로 구분할 수 있도록 서로 다른 정수 ID 번호가 붙어 있다.
Farmer John은 연속한 일부 소들을 골라 사진을 찍으려고 한다. 그런데, 숫자 1부터 6까지와 관련된 어린 시절의 충격적인 사건 때문에, 선택한 소들의 ID 합이 7의 배수인 경우에만 그 소들 사진을 찍으려 한다.

Farmer John이 사진을 찍을 수 있는 소들의 연속한 그룹 중, 가장 많은 소를 포함하는 그룹의 크기를 구하시오.


입력

입력의 첫 줄에는 정수 N이 주어진다. (1 \le N \le 50\,000)

다음 N개의 줄에는 각 줄마다 한 마리 소의 정수 ID가 하나씩 주어진다.
모든 ID는 0 이상 1\,000\,000 이하의 정수이며, 서로 다르다.


출력

ID들의 합이 7의 배수가 되는, 가장 큰 연속한 소 그룹에 포함되는 소의 수를 출력하시오.
만약 그런 그룹이 하나도 없다면 0을 출력한다.

또한 많은 수의 소가 포함된 그룹의 ID 합은 32비트 정수 범위를 넘을 수 있다.
따라서 큰 합을 계산할 때에는 C/C++에서는 64비트 정수형인 long long과 같은 더 큰 자료형을 사용하는 것이 좋다.


예제 

7 
3 
5 
1 
6
2 
14 
10 
5

5+1+6+2+14 = 28



출처

USACO 2016 January Silver
로그인해야 코드를 작성할 수 있어요.