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

snack Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

snack.html

Problem Description

Finally, at the end of the day, it is time for a well-deserved snack. Rar the Cat opens up the pack of green beans he has been keeping all day. However, instead of a pack of beautiful green beans, he finds mud overflowing out of the bag! Oh no! Carefully, he lays out the green beans and mud balls on the table in one line. Since the green beans are all dirty, he has decided to play a game with Kang the Penguin using the dirty green beans and mud.

There are N green beans and mud balls on the table. A green bean with a diameter of D mm will garner Rar the Cat D points. However, a mud ball will decrease Rar the Cat's total points by 2. To win the game, Rar the Cat has to find a consecutive section within the line of green beans and mud balls that can garner him the most points.

Write a program that, when given the profile of the line of green beans and mud balls, outputs the maximum number of points Rar the Cat can get from this game.

Input

The first line of input will contain one integer, N.
The second line of input will contain N characters, containing one of these:
   - a number from '1' to '9', indicating a green bean with that size.
   - 'M', indicating a mudball

Output

Your output should contain one integer, the maximum number of points Rar the Cat can get from this game.
Your output should end with a newline.

Limits

Subtask 1 (30%): 1 <= N <= 100
Subtask 2 (70%): 1 <= N <= 1 000 000

Sample Input 1

5
15M81

Sample Output 1

13

Tags

Maxsum, Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
130101s64MBMinimum
270101s64MBMinimum
3011s64MBMinimum

Judge Compile Command

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