Pagini recente » Cod sursa (job #2745985) | Cod sursa (job #175754) | Cod sursa (job #848704) | Cod sursa (job #2702966) | Cod sursa (job #133827)
Cod sursa(job #133827)
#include<stdio.h>
#define Max 200003
FILE*f=fopen("buline.in","r");
FILE*g=fopen("buline.out","w");
long long s[Max],t[Max],a[Max],smax,inc,sf,lung;
long long n;
void read()
{
fscanf(f,"%lld\n",&n);
long long i,p;
for(i=1;i<=n;++i)
{
fscanf(f,"%lld %lld",&a[i],&p);
if(p==0) a[i]=-1*a[i];
}
}
void ParteaI()
{
long long sc=0,p=1;
sf=1;
inc=1;
long long i;
smax=a[1];
sc=a[1];
for(i=2;i<=n;++i)
{
if(sc<=0)
{
sc=a[i];
p=i;
}
else sc+=a[i];
if(sc>smax)
{
smax=sc;
inc=p;
sf=i;
}
}
lung=sf-inc+1;
}
void ParteaII()
{
long long s[Max],t[Max];
long long i,j,S,pi;
S=smax;
pi=inc;
s[0]=0;
t[0]=0;
for(i=1;i<=n;++i)
{
s[i]=s[i-1]+a[i];
t[i]=t[i-1];
if(s[i]>t[i]) t[i]=s[i];
}
for(i=1;i<=n;++i)
{
if(t[i-1]+s[n]-s[i-1]>smax)
{
smax=t[i-1]+s[n]-s[i-1];
inc=i;
}
}
if(smax>S || inc<pi)
{
long long sum=0;
lung=1;
for(i=inc;;i=i%n+1)
{
sum+=a[i];
if(sum==smax)
{
sf=i;
break;
}
else lung++;
}
}
}
int main()
{
read();
ParteaI();
ParteaII();
fprintf(g,"%lld %lld %lld\n",smax, inc, lung);
return 0;
}