Pagini recente » Cod sursa (job #2393800) | Cod sursa (job #738739) | Cod sursa (job #2493744) | Cod sursa (job #1288005) | Cod sursa (job #642799)
Cod sursa(job #642799)
#include <fstream>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n,k,p,j,a[200000],poz[200000],wpoz[200000],b[200000],x,c,m,R,L,i,w[200000],pz,ad,oz;
int main()
{
f>>n;
for(i=1; i<=n; i++)
{
f>>x>>c;
if (c==0)
a[i]=x*-1;
else a[i]=x;
}
for(i=1; i<=n; i++) w[i]=a[i];
for(i=n-1; i>=1; i--)
{
if (w[i+1]>=0)
{
w[i]+=w[i+1];
wpoz[i]=wpoz[i-1];
}
}
for(i=n; i>=1; i--)
{
if (w[i]>m)
{
m=w[i];
oz=i;
}
w[i]=m;
wpoz[i]=oz;
}
for(i=n+1; i<=2*n; i++)
{
p++;
a[i]=a[p];
poz[i]=p;
b[i]=1;
}
poz[1]=1;
b[1]=1;
for(i=2; i<=n; i++)
{
if (a[i-1]>0)
{
a[i]+=a[i-1];
poz[i]=poz[i-1];
b[i]=b[i-1]+1;
}
else
{
poz[i]=i;
b[i]=1;
}
}
for(i=n+2;i<=2*n;i++)
a[i]+=a[i-1];
for(i=n+1;i<=2*n-1;i++)
{
pz=i-n+1;
k=w[pz];
if (k>0)
{
a[i]+=k;
poz[i]=wpoz[pz];
b[i]=pz+n-wpoz[pz];
}
}
for(i=1; i<=2*n; i++)
{
if (a[i]>m)
{
m=a[i];
R=poz[i];
L=b[i];
}
}
g<<m<<" "<<R<<" "<<L;
f.close();
g.close();
return 0;
}