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

lemonparty Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

statement.html

Problem Description

Coco the Monkey has contracted a strange disease called 'lemon disease' and is going bananas over lemons. He is going to organize a lemon party for all his monkey friends to get them to be addicted to lemons too! There are K monkeys invited to the party (including Coco) and each monkey is to get an equal (non-negative) number of lemons. Coco is going to harvest lemons for his lemon party from the lemon trees. There are N trees in a row and all of them contain lemons, where the ith tree contains Li lemons. Coco is a lazy monkey, so he wants to pick lemons from a contiguous segment of trees, and will pick all the lemons from every tree he visits. He is also a perfectionist, so he wants the total number of lemons he picks to be able to divide among the monkeys such that there are no lemons left after the division. Guess what, he is also a picky monkey! He wants you to determines the number of distinct ways he can pick lemons from the lemon trees that satisfy his requirements.

Wanna go to Coco's lemon party? Then help him find the answer!

Input

The first line of input contains two space separated integers, N and K.
The second line of input contains N integers, which represent the number of lemons on each tree.

Output

Output one integer, the number of ways.

Limits

1 ≤ N ≤ 5000000. 1 ≤ K ≤ 15. 0 ≤ Li ≤ 1000.
Subtask 1 (15%): 1 ≤ N ≤ 500.
Subtask 2 (21%): 1 ≤ N ≤ 5000.
Subtask 3 (8%): 1 ≤ N ≤ 5000000. K = 1.
Subtask 4 (56%): No other constraints apply.
Subtask 5 (0%): Sample testcases.

Sample Input 1

5 3
2 6 8 5 3

Sample Output 1

4

Explanation for Sample 1

(6), (3), (2, 6, 8, 5), (2, 6, 8, 5, 3).

Credits

HCI Mock NOI 2015 backup problem.

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
115251s4MBMinimum
221251s4MBMinimum
38151s4MBMinimum
456311s4MBMinimum
5011s4MBMinimum

Judge Compile Command

g++-8 ans.cpp -o lemonparty -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.