TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Course  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3604
  • Problem
  • P3604平均值
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    给定一个长度为n的01串,选一个长度至少为L的连续子串,使得子串中数字的平均值最大。
    如果有多解,子串长度应尽量小;如果仍有多解,起点编号尽量小。
    序列中字符编号1到n,1<=n<=300000, 1<=L<=3000.

    例如:对于长度为17的序列00101011011011010,如果L=7,最大平均值为6/8(子序列[7,14]);如果L=5,子序列[7,11]平均值最大,为4/5

    Input Format

    第一行,两个整数n和L
    第二行,一个长度为n的01序列

    Output Format

    一行,两个整数,表示所选子序列的起点和终点

    Sample Input

    样例输入1:
    17 5 
    00101011011011010 

    样例输入2:
    20 4 
    11100111100111110000

    Sample Output

    样例输出1:
    7 11 

    样例输出2:
    6 9


    Source  uva1451