Audience count windows
Statement
A street performance team has given N shows so far, and wrote down how many people watched each show. The records are given in order from show 1 to show N.
The team wants to look back on its past shows by grouping X shows in a row into one window. For example, if X is 3, they consider every window of X shows in a row, show 1 through show 3, show 2 through show 4, show 3 through show 5, and so on.
Among these, the team wants the window whose audience counts add up to the most. Several windows may tie for the largest total, so they also want to count how many such windows there are.
Write a program that computes the largest audience total over X shows in a row, together with the number of windows that reach that total.
For example, assume N=7 and X=3. Suppose the audience count of each show is given by the table below.
| Show | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Audience count | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
There are 5 windows of 3 shows in a row. The audience total of each window is given by the table below.
| Window | Shows 1 to 3 | Shows 2 to 4 | Shows 3 to 5 | Shows 4 to 6 | Shows 5 to 7 |
|---|---|---|---|---|---|
| Audience total | 6 | 9 | 12 | 15 | 18 |
The largest total is 18, and the only window with a total of 18 is shows 5 through 7. So the answer for this example is 18 and 1.
Now consider a case where several windows tie for the largest total. Let N=5 and X=1, and let every show have an audience count of 3.
| Show | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Audience count | 3 | 3 | 3 | 3 | 3 |
Since X is 1, each window is a single show, so there are 5 windows. Every window has a total of 3, so the largest total is 3 as well. There are 5 windows with a total of 3, so the answer here is 3 and 5.
X can also be equal to N. Then the only window is show 1 through show N, so the answer is the sum of every show's audience count together with the window count 1.
There is also the case where every show has an audience count of 0, so the largest total is 0. In that case print SAD instead of the total and the window count.
Input and Output Examples
Example 1
Input
7 3 1 2 3 4 5 6 7
Output
18 1
Example 2
Input
5 2 0 0 0 0 0
Output
SAD
Example 3
Input
5 3 10 82 68 74 56
Output
224 1
Input
The first line holds the number of shows N and the number of shows in one window X, separated by a space. N is a natural number from 1 to 250,000, and X is a natural number from 1 to N.
The second line holds the audience counts from show 1 to show N in order, separated by spaces. Each audience count is an integer from 0 to 100.
Output
Print the largest audience total over X shows in a row on the first line. Print the number of windows that reach that total on the second line.
If the largest total is 0, that is, if every show has an audience count of 0, print the single line SAD instead of those two lines.
Requirements
- A window is exactly X shows in a row. Do not count a window of any other length
- The window count means how many windows have a total equal to the largest total
- If the largest total is 0, print the single line SAD
- X is never larger than N
- You must write a program that reads from standard input and writes to standard output
- Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
- The languages you can use are Python and JavaScript
- The memory limit is 256MB. The browser does not measure it, it only states it
- The time limit is set by measuring the setter's reference solution on the same runtime
- On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
- The output has to match the expected value down to the character. A space inside a line counts the same as any other character.
- There are 16 cases, and 3 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
- You have to pass all 16 cases to solve this.
Examples
3 public cases. Judging also uses hidden cases. You have to pass all 16 cases to solve this.
5 3 10 82 68 74 56
224 1
7 3 1 2 3 4 5 6 7
18 1
5 2 0 0 0 0 0
SAD
Solution
Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.
Submitting requires you to log in. Running against the public cases works without one.
You can test with 3 public cases. Submitting runs the hidden cases too.
People who solved this problem
The time shown is the time spent solving. Input reading time is outside the solver's control, so it is excluded. And since each device reports this value itself, we record which device measured it.
Log in and you can see the code once you solve this problem.