## Editorial for BSSPC '21 S3 - James's Egirl Discord Status

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

#### Subtask 1

We can simply loop over all subarrays and find the max sum of a subarray with size divisible by . This can be done efficiently with a prefix sum array or sliding window.

**Time Complexity:**

#### Subtask 2

This subtask was created to reward unoptimized solutions close to a full solution that ran in .

#### Subtask 3

We reduce the problem to instances of the classical maximal subarray problem. For each , we will start from element , constructing a new array of size by compressing every subsequent block of elements into a single element with value equal to their sum; this can be done efficiently with a prefix sum array. Each subarray of this compressed array will correspond to a subarray of with size that is a multiple of . Finding the maximal subarray over all compressed arrays, we arrive at our answer.

**Time Complexity:**

#### Alternate solution

Another solution involves dynamic programming. We let be the minimum sum of a prefix such that and .

The answer will be

**Time Complexity:**

## Comments