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

scanner 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

Desmond the Moon Bear has a scanner :O

He wants to scan through a couple of items

The items must be scanned IN ORDER with the first item being scanned first, then the second item and so on...

However, the scanner comes with a few configurations. In the current configuration, only some items may be scanned

Configurations can be switched, but such a switch is very costly and takes time

In fact, switching from configuration i to j takes abs(i-j) time

Help Desmond find the minimum amount of time required to scan through all the items

Input

The first line of the input contains two integers, n and c, the number of items to be scanned and the number of different configurations

Each subsequent c lines of the input contains of a string of n 0s and 1s. A 0 on line i (starting from 2nd line) on column j (both 0-indexed) indicates the item j cannot be read by configuration i, a 1 indicates that item j can be read by configuration i

Output

Output the minimum amount of time taken to scan all of the items

You are guaranteed there is at least one possible way to scan all of the items

Subtasks

Subtask 1 (15%) n,c<=7

Subtask 2 (30%) n,c<=100

Subtask 3 (55%) n,c<=5000

Sample Testcase 1

Input

5 3
11100
00011
11111
Output
0

Explanation

You don't need to make a switch, just use configuration 3 throughout

Sample Testcase 2

Input

5 5
10000
01000
00100
00010
00001
Output
4

Explanation

Start from config 0, change to config 1, change to config 2, etc. Each of them takes 1 time because they are adjacent

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
115101s256MBMinimum
230101s256MBMinimum
355106s256MBMinimum
4021s256MBMinimum

Judge Compile Command

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