记录编号	264269	评测结果	AAAAAAAAAA
题目名称	单子序列最大和	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-05-28 08:38:17	内存使用	0.79 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
namespace mine{
	int __c,__x,__a[110],__i,__j;
	bool __neg;
	inline int getint(){
		__x=__neg=0;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
		for(;__c>='0'&&__c<='9';__c=getchar())__x=(__x<<1)+(__x<<3)+(__c^48);
		if(__neg)return -__x;
		return __x;
	}
	inline void putint(int __x){
		__neg=__x<0;
		if(__neg)__x=-__x;
		__i=0;
		do{
			__a[__i++]=__x%10+48;
			__x/=10;
		}while(__x);
		if(__neg)putchar('-');
		for(__j=__i-1;__j>=0;__j--)putchar(__a[__j]);
	}
}
using namespace mine;
template<typename T>
struct deque{
private:
	static const int maxn=1000100;
	T a[maxn];
	int head,tail;
public:
	inline deque(){
		head=tail=0;
	}
	inline void clear(){
		deque();
	}
	inline int size(){
		return head>tail?tail-head+maxn:tail-head;
	}
	inline bool empty(){
		return head==tail;
	}
	inline void push_back(const T& n){
		a[tail++]=n;
		if(tail==maxn) tail=0;
	}
	inline T pop_front(){
		T n=a[head++];
		if(head==maxn)head=0;
		return n;
	}
	inline void push_front(const T& n){
		if(head==0)head=maxn+1;
		a[--head]=n;
	}
	inline T pop_back(){
		if(tail==0)tail=maxn+1;
		T n=a[--tail];
		return n;
	}
	inline T& front(){
		return a[head];
	}
	inline T& back(){
		if(tail==0)return a[maxn-1];
		return a[tail-1];
	}
	inline T& end(){
		return a[tail-1];
	}
	inline bool in(const int &n){
		for(int i=0;i<size();i++)if(a[head+i>=maxn?head+n-maxn:head+n]==n)return true;
		return false;
	}
	inline T& operator[](const int& n){
		if(head+n>=maxn)return a[head+n-maxn];
		return a[head+n];
	}
};
int n,num,begin,end,temp=-0x7fffffff;
int sum[1000100]={0};//前缀和，算上自己
deque<int>q;
inline int MAIN(){
#define COGS
#ifdef COGS
	freopen("subq.in","r",stdin);
	freopen("subq.out","w",stdout);
#endif
	n=getint();
	for(int i=0;i<n;i++){
		num=getint();
		sum[i+1]=sum[i]+num;
	}
	for(int i=1;i<=n;i++){
		while(!q.empty()&&sum[q.back()]>=sum[i-1])q.pop_back();
		q.push_back(i-1);
		if(sum[i]-sum[q.front()]>temp){
			temp=sum[i]-sum[q.front()];
			begin=q.front()+1;
			end=i;
		}
	}
	putint(begin);
	putchar(10);
	putint(end);
	putchar(10);
	putint(temp);
	putchar(10);
	return 0;
}
int haha=MAIN();
int main(){;}