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

election Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

election.html

Problem Description

In order to combat potato cruelty in Potatoland, Jiahai is running for election. Jiahai has one competitor, Guan, who is trying to win the election as well. Potatoland consists of a series of N small houses on a straight main road, numbered from 0 to N-1. Before the election, Jiahai has already conducted polls and has found out who each house will vote for.

However, here is the problem. The electorial system is really stupid, and it allows Jiahai to split this road up into segments of at least length L where each segment constitutes an "electorial division". Each electorial division will cast one electorial vote based on its majority. (If Jiahai wins exactly half, Guan has the majority) Jiahai wants to maximise his winning margin, which is defined as (number of electorial votes cast for Jiahai) - (number of electorial votes cast for Guan). Help Jiahai find out what is the maximum possible winning margin. (It can be negative, if Jiahai is sure to lose.)

Input

The first line of input will contain two integers, N and L.
The second line of input will contain N characters, each of them either 'J' or 'G', depending on who the house will vote for.

Output

The output should contain one line with one integer only, representing Jiahai's maximum winning margin.

Limits

Subtask 1 (11%): 1 ≤ N, L ≤ 20.
Subtask 2 (21%): 1 ≤ N, L ≤ 3 000.
Subtask 3 (31%): 1 ≤ N ≤ 300 000. L = 1.
Subtask 4 (37%): 1 ≤ N, L ≤ 300 000.
Subtask 5 (0%): Sample testcases.

Sample Input 1

8 3
JGJGGGGJ

Sample Output 1

0

Sample Input 2

13 3
JJGGJJGGGGJJJ

Sample Output 2

2

Tags

Dynamic Programming, Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
111201s256MBMinimum
221201s256MBMinimum
331201s256MBMinimum
437201s256MBMinimum
5021s256MBMinimum

Judge Compile Command

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