PKU 2796 Feel Good

http://poj.org/problem?id=2796
N要素があって、その中の連続した要素の、
もっとも少ない数＊その要素の合計
がもっとも大きいものを求める。

ヒストグラムのアレです。
幅がありますが累積和でおk。
オーバーフローやすべての要素が0のときに注意。

typedef pair<lint,lint> pi;
int main(){
	int n;scanf("%d",&n);
	stack<pi> s;
	vector<lint> tall(n);
	REP(i,n) scanf("%lld",&tall[i]);
	vector<lint> sum(n+2);
	tall.pb(-1);
	REPN(i,n+2,1)
		sum[i]=sum[i-1]+(lint)tall[i-1];
	lint res=-1;
	int begin,end;
	REP(i,n+1){
		if(s.empty()) s.push(mp(tall[i],i));
		else if(s.top().fr<tall[i]) s.push(mp(tall[i],i));
		else if(s.top().fr>tall[i]){
			int p;
			while(!s.empty() && s.top().fr>=tall[i]){
				pi cur=s.top();s.pop();
				p=cur.sc;
				if(res<(lint)cur.fr*(sum[i]-sum[cur.sc])){
					begin=cur.sc;end=i-1;
					res=(lint)cur.fr*(sum[i]-sum[cur.sc]);
				}
			}
			s.push(mp(tall[i],p));
		}
	}
	printf("%lld\n%d %d\n",res,begin+1,end+1);
	return 0;
}