DMPG '18 S2 - Mimi and K-uteness - DMOJ: Modern 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 \leq A_{i} \leq 10^{9}$

Subtask 1 [10%]

$1 \le N \le 500$ $1 \leq N \leq 500$

Subtask 2 [10%]

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

Subtask 3 [80%]

$1 \le N \le 200\,000$ $1 \leq N \leq 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^{th}$ line being the $k$ $k$ -uteness of the array.

Sample Input

Copy

5
1 1 1 1 1

Sample Output

Copy

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.