DMPG '18 S2 - Mimi and K-uteness

View as PDF

Submit solution

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

Problem type

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



  • 2
    Nils_Emmenegger  commented on Oct. 28, 2020, 6:13 p.m.

    Try using 64 bit integers if you're getting WA on everything except for the test case.