Pagini recente » Cod sursa (job #1484100) | Cod sursa (job #1071912) | Cod sursa (job #2161025) | Cod sursa (job #664300) | Cod sursa (job #1149257)
#include<stdio.h>
#include<deque>
int v[400000],s[400000];
std::deque <int> deq;
int main()
{
FILE *fin,*fout;
fin=fopen("buline.in","r");
fout=fopen("buline.out","w");
int n;
fscanf(fin,"%d",&n);
int i;
for(i=0;i<n;i++)
{
int tip;
fscanf(fin,"%d%d",&v[i],&tip);
if(tip==0)
v[i]=-v[i];
}
for(i=n;i<2*n;i++)
v[i]=v[i-n];
n=2*n;
s[0]=v[0];
for(i=1;i<n;i++)
s[i]=s[i-1]+v[i];
int smax=0,poz=0,l=0;
for(i=0;i<n;i++)
{
while(!deq.empty()&&s[i]<=s[deq.back()])
deq.pop_back();
deq.push_back(i);
if(deq.front()==i-n/2)
deq.pop_front();
if(smax<s[i]-s[deq.front()])
{
smax=s[i]-s[deq.front()];
poz=deq.front()+1;
l=i-poz+1;
}
}
fprintf(fout,"%d %d %d",smax,poz+1,l);
return 0;
}