oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

rarsum Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

rarsum.html

Problem Description

Rar the cat is actually a programmer. So he has a programming problem for you guys to solve: Max Sum. However, he finds this too easy and classic to be used as a selection test problem, especially for RI programmers! They need some challenge, don't they? Therefore, he has made a variant of max sum, known as the Rar Sum.

Rar Sum is extremely similar to Max Sum. You are provided with a list of N integers, whereby you have to find out the largest contiguous sub-array with the largest sum. However, the challenge Rar has added is that the sub-array length must be a multiple of K and also must have at least L elements.

Input

You are to input from standard input.

The first line consists of 3 integers, in the following order N, K, L

The second line consists of N space separated integers, the list of N integers in which you have to find the Rar Sum from.

Output

You are to output to standard output.

Output a single integer, the sum value of the largest contiguous sub-array with the largest sum that has at least L elements and its length is a multiple of K.

Do note that the sub-array can be of length 0 if L is 0.

Limits

All the numbers in the provided list of N integers will be in the range of -1000 to 1000 unless otherwise stated in the subtasks (Eg. Subtask 1, 2)

The lowest multiple of K, that is larger than L is guaranteed to be not larger than N.

Subtask 1 (2%): N ≤ 100, K = 1, L = 0. All numbers in the list of N integers are guaranteed to be positive. (There are basically no restrictions on sub-array length)

Subtask 2 (3%): N ≤ 100, K ≤ N, L = 0. All numbers in the list of N integers are guaranteed to be positive.

Subtask 3 (6%): N ≤ 1000, K = 1, L = 0. (There are basically no restrictions on sub-array length)

Subtask 4 (12%): N ≤ 1000000, K = 1, L = 0. (There are basically no restrictions on sub-array length)

Subtask 5 (9%): N ≤ 1000, K ≤ N, L = 0.

Subtask 6 (13%): N ≤ 1000000, K ≤ N, L = 0.

Subtask 7 (9%): N ≤ 1000, K = 1, L ≤ N.

Subtask 8 (13%): N ≤ 1000000, K = 1, L ≤ N.

Subtask 9 (12%): N ≤ 1000, K ≤ N, L ≤ N.

Subtask 10 (21%): N ≤ 1000000, K ≤ N, L ≤ N.

Subtask 11 (0%): As per sample testcases.

Sample Testcase 1

Input:

10 1 0
1 2 3 4 5 6 7 8 9 10

Output:

55

The Rar Sum for this case is the summation of all the integers in the provided array.

Sample Testcase 2

This testcase adheres to the limits of subtask 2, 5, 6, 9, 10 only.

Input:

10 4 0
1 2 3 4 5 6 7 8 9 10

Output:

52

The Rar Sum for this case is the summation of all the integers except the first two, since the length of the subarray must be a multiple of 4.

Sample Testcase 3

This testcase adheres to the limits of subtask 3 to 10 only.

Input:

10 1 0
7 -12 8 -9 -3 20 -1 -2 9 3

Output:

29

The subarray for this case is [20 -1 -2 9 3].

Sample Testcase 4

This testcase adheres to the limits of subtask 5, 6, 9, 10 only.

Input:

10 3 0
7 -12 8 -9 -3 20 -1 -2 9 3

Output:

26

The subarray for this case is [-3 20 -1 -2 9 3].

Sample Testcase 5

This testcase adheres to the limits of subtask 7 to 10 only.

Input:

10 1 5
-1 -2 -3 -4 5 -6 -7 8 -9 -10

Output:

-4

The subarray for this case is [-4 5 -6 -7 8] since the subarray's length must be at least 5.

Sample Testcase 6

This testcase adheres to the limits of subtask 9, 10 only.

Input:

10 4 5
-1 -2 -3 -4 -5 -6 -7 -8 -9 -10

Output:

-36

The subarray for this case is [-1 -2 -3 -4 -5 -6 -7 -8] since the subarray's length must be at least 5 and also be a multiple of 4.

rarsum.pdf

Your browser does not support embedded PDF files. Please download the PDF instead.

rarsum.docx

Tags

Raffles Cat Helping Contest 2013

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1221s64MBMinimum
2351s64MBMinimum
36101s64MBMinimum
412101s64MBMinimum
59101s64MBMinimum
613101s64MBMinimum
79101s64MBMinimum
813101s64MBMinimum
912101s64MBMinimum
1021101s64MBMinimum
11061s64MBMinimum

Attachments

Attachment Filesize Last Updated
rarsum_sample.zip1.57KB31 Jan 2013, 15:10:30

Judge Compile Command

g++-8 ans.cpp -o rarsum -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.