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

barcode 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

Gug is having fun with barcodes! A barcode is a string of 0s and 1s. Gug will only be happy if the 1s in the barcode can be divided into consecutive sections of length X to Y. Note that 2 consecutive sections of 1 do not need to be divided by a 0 in between.

Gug is able to edit the barcode by changing 0 to 1 or 1 to 0 at chosen position(s) in the barcode. Given a barcode of length N, find the minimum operations it takes for Gug to be happy.

Input

The first line of input will contain a 3 integers, N, X, Y.

The second line of input will contain a string of length N, representing the barcode.

Output

The output should contain one integer representing the minimum number of operations it takes for Gug to be happy if he starts with the given barcode.

Limits

Subtask 1 (30%): 1 ≤ N ≤ 103, 0 ≤ X, Y ≤ N.

Subtask 2 (31%): 1 ≤ N ≤ 105, 0 ≤ X = Y ≤ N.

Subtask 3 (39%): 1 ≤ N ≤ 105, 0 ≤ X, Y ≤ N.

Subtask 4 (0%): Sample Testcases.

Sample Input 1

8 3 4
01010101

Sample Output 1

2

Explanation

Gug changes the barcode from 01010101 to 01110111, taking 2 operations.

Sample Input 1

8 4 5
10001010

Sample Output 1

3

Explanation

Gug changes the barcode from 10001010 to 00001111, taking 3 operations.

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
130201s256MBMinimum
231201s256MBMinimum
339601s256MBMinimum
4021s256MBMinimum

Judge Compile Command

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