Pagini recente » Cod sursa (job #655725) | Cod sursa (job #389651) | Cod sursa (job #733996) | Cod sursa (job #591416) | Cod sursa (job #79194)
Cod sursa(job #79194)
# include <stdio.h>
const long int MAXN=400000;
long int n,v[MAXN+1],sm,pim,pfm,count;
struct {long int pos,sum;} deq[MAXN+1];
void citire()
{
FILE *f=fopen("buline.in","r");
fscanf(f,"%ld",&n);
long int i,aa;
for (i=1;i<=n;i++)
{
fscanf(f,"%ld%ld",&v[i],&aa);
if (!aa) v[i]*=-1;
v[n+i]=v[i];
}
fclose(f);
}
void scrie()
{
FILE *g=fopen("buline.out","w");
fprintf(g,"%ld %ld %ld\n",sm,pim,pfm);
fcloseall();
}
void calculeaza()
{
sm=v[1];pim=1;pfm=1;count=1;
long int i;
long int prim=0,ultim=0;
deq[0].sum=0;deq[0].pos=0;
for (i=2;i<=2*n-1;i++)
{
v[i]+=v[i-1];
//bagam in deq cel mai nou elem
++ultim;
deq[ultim].pos=i-1;
deq[ultim].sum=v[i-1];
//scufundam in deq, dar nu si pentur egal
while (ultim>prim&&deq[ultim].sum<deq[ultim-1].sum)
{
ultim--;
deq[ultim].pos=deq[ultim+1].pos;
deq[ultim].sum=deq[ultim+1].sum;
}
//verificam solutia
if (sm<v[i]-deq[prim].sum)
{
sm=v[i]-deq[prim].sum;
pim=deq[prim].pos+1;
pfm=i-deq[prim].pos;
}
//scoatem din deq tot ce se poate
while (i+1-deq[prim].pos>n&&prim<=ultim) prim++;
}
}
int main()
{
citire();
calculeaza();
scrie();
return 0;
}