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

supermarket Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

supermarket.html

Problem Description

Gug is lazy to get out of his house, so he has tasked his AI to go grocery shopping for him. At the store, the AI has found a row of N mushrooms lined up in a row, numbered 0 to N-1 from left to right. The ith mushroom has deliciousness Di, and weight Wi grams. Some mushrooms can be rotten, and so can have negative deliciousness.

Gug wishes to buy a consecutive segment of mushrooms (or no mushrooms at all). Unlike Gug, his AI is weak, and so can only carry a maximum of X grams of mushrooms before it collapses and dies. Help Gug choose a consecutive segment of mushrooms to buy such that the sum of their deliciousness is maximised.

Input

The first line of input will contain two integers, N and X.

The second line of input will contain N integers, representing the array D.

The third line of input will contain N integers, representing the array W.

Output

The output should contain one line with exactly one integer, the maximum sum of deliciousness of any valid segment of mushrooms the AI can buy.

Limits

For all subtasks: 0 ≤ X ≤ sum of Wi, |Di| ≤ 106, 1 ≤ Wi ≤ 106.

Subtask 1 (8%): 1 ≤ N ≤ 300.

Subtask 2 (24%): 1 ≤ N ≤ 2000.

Subtask 3 (17%): 1 ≤ N ≤ 200000, X = sum of Wi.

Subtask 4 (19%): 1 ≤ N ≤ 200000, Di ≥ 0.

Subtask 5 (18%): 1 ≤ N ≤ 200000.

Subtask 6 (14%): 1 ≤ N ≤ 3000000.

Subtask 7 (0%): Sample Testcases.

Sample Input 1

6 20
5 -1 2 -4 6 7
3 1 4 1 9 15

Sample Output 1

8

Sample Input 2

2 4
-1 -2
1 3

Sample Output 2

0

Tags

Data Structure, Sliding Window

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
18222s256MBMinimum
224422s256MBMinimum
317212s256MBMinimum
419202s256MBMinimum
5181022s256MBMinimum
6141122s256MBMinimum
7022s256MBMinimum

Judge Compile Command

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