TSSPC Contest 1 P4 - Halloween Spooking

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 3.0s
Memory limit: 64M
PyPy 3 150M

Authors:
Problem type

It's Halloween again! Little sankeeth_ganeswaran goes scaring people in his neighbourhood. Each neighbour he visits has a certain amount of Trehalose (noise tolerance). Some neighbours are easily scared and some are quite fearless! This is very sad for sankeeth_ganeswaran whose voice can only scream M Trehalose. There are N houses numbered 1 to N. Each house h_i has a Trehalose tolerance of m_i. Output the largest range of houses sankeeth_ganeswaran can spook in a consecutive row.

Input Specification

The first line contains an integer N, the number of houses followed by M, the amount of Trehalose sankeeth_ganeswaran can scream.

The next N lines will contain the integer m_i the neighbour's Trehalose tolerance.

Output Specification

On one line, print the integers a and b denoting the range of the most consecutive houses Sankeeth can scare (inclusive).

If there is more than one solution, output the first occurrence.

Constraints

For all subtasks:

1 \le N \le 1\,000\,000

1 \le M \le 10\,000

1 \le m_i \le M

Subtask 1 [10%]

N \le 10

Subtask 2 [20%]

N \le 1\,000

Subtask 3 [70%]

No further constraints.

Sample Input

5 1000
700
300
200
10
850

Sample Output

2 4

Sample Explanation

Starting at house 2 ending at house 4, Sankeeth screams at 3 neighbours using 300 + 200 + 10 trehalose.


Comments

There are no comments at the moment.