#3191. 「ROI 2019 Day2」花环

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

译自 ROI 2019 Day2 T1. Гирлянда

对于一个 01 串,如果它可以被表示为 A1A1A……1A 的形式,其中

  • A 是若干个 0 或空串,且
  • 每个 A 包含的 0 数量相等,且
  • 首尾都是 A,中间有至少一个 1

则称这是一个「美丽的」01 串。

给一个 01 串,请删除尽量少的数字,使得剩下的数字形成一个美丽的 01 串。


Гирлянда — это цепочка из элементов: флажков и шариков, содержащая хотя бы один флажок. Длиной гирлянды называется количество элементов, из которых она состоит.

Гирлянда считается красивой, если для каждого флажка количество подряд идущих шариков слева от него до ближайшего слева флажка или до начала гирлянды равно количеству подряд идущих шариков справа от него до ближайшего справа флажка или до конца гирлянды.

Обозначим шарик символом «0», а флажок — символом «1». Например, гирлянда «0001000» является красивой, а гирлянда «001010» — нет, поскольку слева от первого флажка два шарика, а справа от него — один шарик. Отметим, что цепочка «000» не является гирляндой, так как не содержит ни одного флажка.

Задана гирлянда, разрешается удалить некоторые её элементы.

Требуется написать программу, находящую по описанию гирлянды самую длинную красивую гирлянду, которую можно получить из заданной удалением элементов.

样例

样例 1

10
0100100000
7
0001000

样例 2

3
111
3
111

样例 3

7
0100101
5
01010

数据范围与提示

对于所有数据, 1 ⩽ n ⩽ 500000

k 表示输入的 01 串中 1 的个数。

子任务 # 分值 n ⩽ k ⩽
1 20 15
2 20 1000 2
3 20 15
4 16
5 10 100000 50
6 14 500000