## COCI '10 Contest 5 #5 Dvoniz

View as PDF

Points: 12 (partial)
Time limit: 0.5s
Memory limit: 64M

Problem types

We say that a sequence of elements is interesting if neither the sum of the first elements, nor the sum of the last elements, is greater than .

A sequence of length is given. For every element, output the length of the longest interesting subsequence starting with that element.

#### Input Specification

The first line contains integers and .

The following lines contain the sequence , one integer per line. The integers are positive and their sum does not exceed .

#### Output Specification

Output must consist of lines. line must contain one integer, the length of the longest interesting subsequence starting with the element. If an interesting subsequence at that position doesn't exist, output (zero).

#### Sample Input 1

5 10000
1
1
1
1
1

#### Sample Output 1

4
4
2
2
0

#### Sample Input 2

5 9
1
1
10
1
9

#### Sample Output 2

2
0
0
2
0

#### Sample Input 3

8 3
1
1
1
1
1
1
1
1

#### Sample Output 3

6
6
6
4
4
2
2
0

• commented on May 16, 2022, 8:32 p.m.

Since the original data were weak, an additional test case was added and weighted a third of the points.

• commented on March 19, 2021, 1:53 p.m.

Fast I/O go brrrr.

• commented on March 19, 2021, 9:00 p.m.

Time limit has been reduced to 0.5s so brute force should no longer pass.

• commented on March 17, 2021, 9:22 p.m.

Note that when this problem mentions "subsequence", it actually means "subarray"