问题1673--【USACO】Pasture Fences

1673: 【USACO】Pasture Fences

时间限制: 1 Sec  内存限制: 64 MB
提交: 14  解决: 5
[提交] [状态] [讨论版] [命题人:]

题目描述

Farmer John has a long fence made of fence poles and rails. Each of the N (1 <= N <= 3000) fence poles carries a sign with a single number from -1000 through +1000. Some poles might have the same number on their sign as other poles. While chewing their cud, the cows made up a game. The cow who can find the "best fence sum" gets ice cream for dessert. To win the game, the winning cow must find the longest contiguous set of poles whose sum has the smallest absolute value. Help them determine the winning sum.

输入

* Line 1: One line with a single integer: N * Lines 2..N+1: Each line contains a pole's label. Line 2 contains the value for pole with sequence number 1, etc.

输出

A single line with three numbers: * the sequence number of the pole that is first to be summed, * the sequence number of the pole that is last to be summed, and * the absolute value of the sum of the labels of those poles. If more than one sequence has the same "best fence sum" and same maximum length, report the sequence with the lowest first sequence number.

样例输入 复制

6 5 10 -5 -6 2 4

样例输出 复制

4 6 0

来源/分类


[提交] [状态]