DMPG '18 S2 - Mimi and K-uteness - Olympiads Online Judge

DMPG '18 S2 - Mimi and K-uteness

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

Kirito

Problem type

Mimi decides to play a game with the following rules:

A $k$ ~k~-subarray is a subarray of length $k$ ~k~.

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

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

Constraints

For all subtasks:

$1 \le A_i \le 10^9$ ~1 \le A_i \le 10^9~

Subtask 1 [10%]

$1 \le N \le 500$ ~1 \le N \le 500~

Subtask 2 [10%]

$1 \le N \le 2\,000$ ~1 \le N \le 2\,000~

Subtask 3 [80%]

$1 \le N \le 200\,000$ ~1 \le N \le 200\,000~

Input Specification

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

Output Specification

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

Sample Input

5
1 1 1 1 1

Sample Output

Comments

3

Nils_Emmenegger commented on Oct. 28, 2020, 10:13 p.m.

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