#A. 琉金云间

    传统题 1000ms 256MiB

琉金云间

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Yoimiya 有 nn 堆火药,有一个长度为 nn 的 01 字符串描述这些火药,第 ii 堆火药能点燃当且仅当 ai=1a_i=1

假设当前还剩 mm 堆火药,编号从小到大依次为 1,2,,m1,2,\cdots,m,可以选择一堆能点燃的火药 ii,将其点燃,其会引爆第 (mi+1)(m-i+1) 堆火药并让其消失,但第 ii 堆火药不会消失并且在此后依然能被点燃。

注意,虽然火药的编号变了,但是可燃性不会改变。

Yoimiya 想要烟火尽可能地为世人绽放,请求出至多能点燃几次火药。

输入格式

第一行,一个整数 nn

第二行,一个长度为 nn 的 01 字符串 aa

输出格式

一个整数,代表答案。

样例 11 输入

5
00100

样例 11 输出

1

样例 22 输入

5
01010

样例 22 输出

3

样例解释

样例一:只能点燃 a3a_3

样例二:其中一种最优操作为:

点燃 a4=1a_4=1,使得 a2a_2 消失,字符串变为 0010

之后点燃一次 a3=1a_3=1,字符串变为 010

点燃一次 a2=1a_2=1,字符串变为 00

一共点燃 33 次。

测试点约束

对于 100%100\% 的数据,1n106,ai{0,1}1\leq n\leq 10^6,a_i\in\{0,1\}

各测试点的约束如下表所示,其中 cc 表示字符串中有多少字符 1

测试点编号 nn\leq cc\leq
11 55 nn
22 1212
343\sim 4 50005000
55 10610^6 11
66 22
7107\sim 10 nn

[YDRG#002] 提瓦特环游记(下) · 云斗杯 · 八月 Golden 组模拟赛

未参加
状态
已结束
规则
北斗IOI
题目
6
开始于
2023-8-8 18:00
结束于
2023-8-8 22:30
持续时间
4.5 小时
主持人
参赛人数
299