| 比赛 | 
    20160412 | 
    评测结果 | 
    AWAWWAWAAAWAWWAWAAWW | 
    | 题目名称 | 
    非负的部分和 | 
    最终得分 | 
    50 | 
    | 用户昵称 | 
    Satoshi | 
    运行时间 | 
    2.335 s  | 
    | 代码语言 | 
    C++ | 
    内存使用 | 
    38.46 MiB  | 
    | 提交时间 | 
    2016-04-12 10:02:43 | 
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <cstring>
#define N 1000010
using namespace std;
ifstream in("sumc.in");
ofstream out("sumc.out");
int sum[N]={0},s[N]={0};
int n,minum;
int INF=2147483636-100000;
int ans=0;
class rangetree
{
public:
	int setv[4*N];
	int minv[4*N];
	void clear()
	{
		memset(setv,0,sizeof(setv));
		memset(minv,0,sizeof(minv));
	}
	void pushup(int o)
	{
		minv[o]=min(minv[o<<1],minv[o<<1|1]);
	}
	void modify(int o,int l,int r,int x,int v)
	{
		if(l==r)minv[o]=v;
		else
		{
			int mid=(l+r)>>1;
			if(x<=mid)modify(o<<1,l,mid,x,v);
			else modify(o<<1|1,mid+1,r,x,v);
			pushup(o);
		}
	}
	int query(int o,int l,int r,int ql,int qr)
	{
		int mid=(l+r)>>1;
		if(ql<=l&&r<=qr)return minv[o];
		int ans=INF;
		if(ql<=mid)ans=min(ans,query(o<<1,l,mid,ql,qr));
	    else ans=min(ans,query(o<<1|1,mid+1,r,ql,qr));
		return ans;
	}
}A;
void read()
{
	int i;
	in>>n;
	minum=INF;
	for(i=1;i<=n;i++)
	{
		in>>s[i];
		sum[i]=sum[i-1]+s[i];
	}
	//out<<minum<<endl;
}
void work()
{
	int i,L,R;
	A.clear();
	//A.modify(1,1,n,0,INF);
	for(i=1;i<=n;i++)A.modify(1,1,n,i,sum[i]);
	for(i=1;i<=n;i++)
	{
	    L=A.query(1,1,n,i,n)-sum[i-1];
		if(i>1)R=A.query(1,1,n,1,i-1)+sum[n]-sum[i-1];
		else R=INF;
		if(L>=0&&R>=0)ans++;
	}
	out<<ans<<endl;
	//for(i=1;i<=n;i++)out<<A.query(1,1,n,i,i)<<endl;
}
int main()
{
	//out<<INF<<endl;
	read();
	work();
	return 0;
}