Pagini recente » Cod sursa (job #402603) | Cod sursa (job #145359) | Cod sursa (job #835147) | Cod sursa (job #456789) | Cod sursa (job #329964)
Cod sursa(job #329964)
#include<fstream>
#define maxn 400002
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int a[maxn],i,j,deque[maxn],n,s[maxn],p,q,x,y,tmax;
void add(int x)
{
while(q>=p&&s[deque[q]]>=s[x])
--q;
deque[++q]=x;
}
void calib(int x)
{
while(deque[p]<=x)
++p;
}
int main()
{
f>>n;
for(i=1;i<=n;++i)
{
f>>a[i]>>j;
if(!j)
a[i]=-a[i];
a[n+i]=a[i];
}
n*=2;
s[1]=a[1];
for(i=2;i<=n;++i)
s[i]=s[i-1]+a[i];
p=1;
q=1;
x=1;
y=1;
tmax=-0x3f3f3f3f;
for(i=1;i<n;++i)
{
if(s[i]-s[deque[p]]>tmax)
tmax=s[i]-s[deque[p]],x=deque[p]+1,y=i;
add(i);
if(i>(n>>1))
calib(i-(n>>1));
}
g<<tmax<<" "<<x<<" "<<y-x+1<<"\n";
f.close();
g.close();
return 0;
}