DMPG '18 S2 - Mimi and K-uteness

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Mimi decides to play a game with the following rules:

A k-subarray is a subarray of length k.

The k-uteness of an array A is defined as the sum of the sum of all k-subarrays of A.

The winner is the person who can output the k-uteness of A for k = 1, 2, 3, \ldots N, where N is the number of elements in A. Can you beat Mimi?


For all subtasks, 1 \le A_i \le 10^9.

Subtask 1 [10%]

1 \le N \le 500

Subtask 2 [10%]

1 \le N \le 2\,000

Subtask 3 [80%]

1 \le N \le 200\,000

Input Specification

The first line of input will contain a single integer, N.
The next line of input will contain N space separated integers, A_1, A_2, \ldots, A_N.

Output Specification

N lines, with the k^{\text{th}} line being the k-uteness of the array.

Sample Input

1 1 1 1 1

Sample Output



There are no comments at the moment.