Back To School '18: Making Friends

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 0.3s

Java 1.0s

Python 1.0s

Memory limit: 64M

Java 128M

Python 256M

Author:

Beautiful_Times

Problem type

The school year is starting soon, so Yunji wants to make some friends through his school's Discord server. In the server, there are $N$ ~N~ calls simultaneously going on, each with $M_i$ ~M_i~ participants.

Unfortunately, ~~everyone from Yunji's school dislikes him~~ everyone has important things to do other than Discord, so for every minute he is in the $i^\text{th}$ ~i^\text{th}~ call, $1$ ~1~ person will leave that call forever. However, if he is not in that call, no one will leave the call.

Yunji has $X$ ~X~ minutes before school starts. At the beginning of each minute, he can either leave the current call and join a different call, or stay in the current call. The quality of each call is defined as the sum of the number of participants (excluding Yunji) for every minute he stays in that call. Note that there can't be negative participants in the call, so the sum is capped at $0$ ~0~.

The total quality is the sum of the qualities of every call $i$ ~i~ $(1 \le i \le N)$ ~(1 \le i \le N)~. If he does not ever join a call $i$ ~i~, the quality of call $i$ ~i~ is $0$ ~0~.

Help Yunji maximize the total quality.

Input Specification

The first line will contain $2$ ~2~ integers, $N, X$ ~N, X~ $(1 \le N \le 10^5, 1 \le X \le 10^4)$ ~(1 \le N \le 10^5, 1 \le X \le 10^4)~.

The second line will contain $N$ ~N~ integers, $M_1, M_2, \dots, M_N$ ~M_1, M_2, \dots, M_N~ $(1 \le M_i \le 10^9)$ ~(1 \le M_i \le 10^9)~.

Output Specification

Output the maximum total quality that Yunji can achieve through strategically hopping between calls.

Constraints

Subtask 1 [5%]

$M_i = M_{i+1}$ ~M_i = M_{i+1}~ for all $1 \le i \le N$ ~1 \le i \le N~.

Subtask 2 [15%]

$N \le 100$ ~N \le 100~

Subtask 3 [80%]

No additional constraints.

Sample Input 1

2 2
9 3

Sample Output 1

Explanation for Sample 1

Yunji can spend all his time in the first call: if he does there will be 9 participants in the call in the first minute, and 8 participants in the second minute. The quality of this call would be $9 + 8 = 17$ ~9 + 8 = 17~. The total quality would be $17 + 0 = 17$ ~17 + 0 = 17~.

Sample Input 2

2 3
5 6

Sample Output 2

Explanation for Sample 2

Yunji can spend the first minute in call $1$ ~1~, for a quality of $5$ ~5~. He can then spend two minutes in call $2$ ~2~, for a quality of $6 + 5 = 11$ ~6 + 5 = 11~. The total quality is therefore $5 + 11 = 16$ ~5 + 11 = 16~.

Comments

0

sankeeth_ganeswaran commented on March 20, 2019, 12:41 a.m.

My code seems to be failing a test case and I can't figure out why, can someone take a look?

1

Beautiful_Times commented on March 20, 2019, 12:49 a.m.

There cannot be negative participants in a call, so make sure you're not adding negative numbers to your sum.

0

sankeeth_ganeswaran commented on March 20, 2019, 2:25 a.m.

Oh I see, thanks!

-2

JimmyDeng12345 commented on Sept. 11, 2018, 1:57 a.m.

Is there any special cases in this problem? The third test case of every batch gives me a WA.

1

kingW3 commented on Sept. 11, 2018, 10:23 a.m.

Your sum may be $>2^{31}$ ~>2^{31}~ so the int type overflows.