Pagini recente » Cod sursa (job #2372742) | Cod sursa (job #2976205) | Cod sursa (job #1894422) | Cod sursa (job #1192107) | Cod sursa (job #25474)
Cod sursa(job #25474)
#include<stdio.h>
#define dim 2000002
int a[dim];
int n;
int max,poz;
int x[dim],y[dim];
int i,j,i1=1;
int smax,pozinceput,pozsf;
int sumarosii,sumanegre;
void citire();
void dinamica();
void afisare();
void solve();
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
citire();
solve();
dinamica();
afisare();
return 0;
}
void citire()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d %d",&x[i],&y[i]);
}
void solve()
{
max=-32000;
for(i=1;i<=n;i++)
{
if(y[i]==0)
sumanegre+=x[i];
else
sumarosii+=x[i];
}
if(sumarosii>sumanegre)
poz=1;
else
poz=0;
for(i=1;i<=n;i++)
a[i]=i;
for(i=n+1;i<=(2*n-1);i++)
a[i]=i-n;
for(i=1;i<=(2*n-1);i++)
if(y[i]==0 && poz==1)
a[i]=-x[i];
else
a[i]=x[i];
for(i=1;i<=(2*n-1);i++)
if(poz==0)
if(y[i]==1)
a[i]=-x[i];
else
a[i]=x[i];
for(i=n+1;i<=(2*n)-1;i++)
a[i]=a[i-n];
}
void dinamica()
{
int s=0,i;
for(i=1;i<=(2*n-1);i++)
if(a[i]+s>smax)
{
s+=a[i];
smax=s;
i1=i1;
pozsf=i;
//if(pozsf>n) break;
}
else
if(a[i]+s>0)
s+=a[i];
else
{
s=0;
i1=i+1;
}
}
void afisare()
{
printf("%d %d %d",smax,i1,pozsf-i1+1);
}