子串平均值
时间限制:1秒 内存限制:256M
【题目描述】
给定一个长度为 \(n\) 的 01 串,选一个长度至少为 L 的连续子串,使得子串中数字平均值最大。如果有多解,子串长度应尽量小;如果仍然有多解,起点编号应尽量小。序列中的字符编从左到右依次编号为 \(1..n\),因此 \([1,n]\) 就是完整的字符串。
例如,对于如下长度为 17 的序列 00101011011011010,如果 \(L=7\),最大平均值为 6/8(子序列为 [7,14],其长度为8 );如果 \(L=5\),子序列为 [7,11] 的平均值最大为 4/5。
【输入格式】
第包含两行,第 1 行是 \(n\) 和 \(L\),第 2 行长度为 \(n\) 的 01 串。
【输出格式】
包含 2 个整数,第一行最大平均值,用最简分数表示,格式如样例;第2行的两个整数表示平均值最大序列的起点和终点。
【输入输出样例1】
Input
17 5
00101011011011010
Output
4/5
7 11
【输入输出样例2】
Input
20 4
11100111100111110000
Output
1/1
6 9
【数据限制】
对于 \(100\%\) 的数据,\(1≤n≤1000000\),\(1≤L≤1000\)。
【来源】
Mr.he