시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 200 | 50 | 31 | 25.620% |
Coder's High 2014의 예비소집을 위해 명우는 아래와 같은 간단한 문제를 준비했다.
크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있다.
여러분은 N과 배열 X가 주어졌을 때, X의 maximum subarray의 합을 구하자. 즉, max1 ≤ i ≤ j ≤ N (X[i]+...+X[j])를 구하자.
명우는 데이터를 만들 때 각 Xi를 어떤 두 정수 Ai, Bi에 대해 Ai ≤ Xi ≤ Bi을 만족하게 만들기로 정했다. N도 정한 명우는 이제 데이터를 만들려고 하였는데, 문득 답이 D가 되는 서로 다른 입력데이터의 개수가 몇 개 일지 궁금해졌다.
입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 두 정수 N (1 ≤ N ≤ 1,000)과 D (-1,000 ≤ D ≤ 1,000)가 공백으로 구분되어 주어진다.
다음 N개의 줄의 i번째 줄에는 Ai, Bi (-1,000 ≤ Ai ≤ Bi ≤ 1,000)가 공백으로 구분되어 주어진다.
각 테스트 케이스마다 한 줄에 답이 D 가 되는 입력의 개수를 1,000,000,007로 나눈 나머지를 출력한다.
2 3 3 -1 2 -1 2 -1 2 5 3 -1 5 -2 3 -4 5 -2 3 -2 6
12 1897
첫 번째 예제에서 답이 3인 X는 아래의 12개이다.
(-1,1,2) (-1,2,1) (0,1,2) (0,2,1) (1,0,2) (1,1,1)
(1,2,-1) (1,2,0) (2,-1,2) (2,0,1) (2,1,-1) (2,1,0)
Contest > Coder's High > Coder's High 2014 H번