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

phototaking Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

phototaking.html

Problem Description

Recently, Damian discovered an old camera lying around his house. Curious, he decides to take it out for a spin and go around phototaking.

On the streets, he spots a collection of N assorted items on display in a row at a museum's window. He then evaluates each item and assigns them each an awesomeness index Ai.

He decides to take photographs of the collection of items. Obviously, he can only take photos of contiguous ranges of items.

However, he prefers to take ordinary photos. Thus, he wants to know how many (contiguous) ranges exist such that the sum of the awesomeness indices of the elements in the range is no larger than a threshold S.

Input

The first line contains two integers, N and S, the number of items and the threshold.

The second line contains N space-separated integers, with the ith integer representing the awesomeness index of the ith item.

Output

The output should contain one line containing one integer, the number of ranges that sum up to no larger than the threshold.

Limits

For all subtasks, 0 ≤ Ai ≤ 106.

Subtask 1 (7%): 1 ≤ N ≤ 106; S = 1012.

Subtask 2 (11%): 1 ≤ N ≤ 500; 0 ≤ S ≤ 108.

Subtask 3 (13%): 1 ≤ N ≤ 10 000; 0 ≤ S ≤ 108.

Subtask 4 (47%): 1 ≤ N ≤ 105; 0 ≤ S ≤ 108.

Subtask 5 (23%): 1 ≤ N ≤ 107; 0 ≤ S ≤ 108.

Subtask 6 (0%): Sample Testcases.

Sample Testcase 1

Input

5 4
0 3 1 2 4

Output

9

Sample Output 1 Explanation

The ranges are {0}, {3}, {1}, {2}, {4}, {0, 3}, {3, 1}, {1, 2} and {0, 3, 1}.

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1760.9s256MBMinimum
21160.9s256MBMinimum
31360.9s256MBMinimum
44660.9s256MBMinimum
52370.9s256MBMinimum
6010.9s256MBMinimum

Judge Compile Command

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