1242. 小新的问题

时间限制 1000 ms   内存限制 128 MB

    小新最喜欢的运动就是睡觉了,因为睡眠是精力恢复的重要保证。每次小新睡醒,他的脑海里总会浮现出一些奇怪的想法。某天醒来,他突然想到一个问题:     对于一个长度为N的整数序列:A[1],A[2],...,A[N]。如果我们定义它的一个长度为M的K邻子序列为:A[P1],A[P2],...,A[PM];其中满足1< =K< N,1< =P1< P2< ...< PM< N且P2-P1=P3-P2=...=PM-P(M-1)=K (注意,M=1,即子序列只包含一个数时,也认为它是一个合法的K邻子序列)。     S(K)表示给定序列中的一个和最大的K邻子序列的和。小新想知道这些S(1),S(2),...,S(N-1)中的最大值是多少,你可以帮他回答这个问题么?(序列的和为一个序列中所有数的总和。)

输入数据

&nbsp &nbsp 第一行是一个整数N,表示序列的长度。
&nbsp &nbsp 第二行是N个整数,分别表示A[1],A[2],...,A[N]。相邻数字由一个空格隔开。序列整数的绝对值不大于32767.

输出数据

&nbsp &nbsp 输出包括一行:最大的S(K)及其对应的K,用一个空格隔开,行尾使用回车符换行。若存在多个K其S(K)等于最大值,则输出较小的K。

样例输入

复制
5
1 -5 4 5 -20
 \n
 ·  · · ·   \n

样例输出

复制
9 1
 · \n

样例说明

【样例说明】
&nbsp &nbsp S(1)=9,对应子序列为(4&nbsp 5);S(2)=5,对应子序列为(1&nbsp 4)或(5);S(3)=6,对应子序列为(1&nbsp 5);S(4)=5,对应子序列为(5)。
【数据范围】
对于所有的数据2< =N< =10000

提交

请先 登录

Source

GDOI第二试第一题

© 2024 FAQs Contact About