比赛 |
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;
}