Cod sursa(job #642807)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 2 decembrie 2011 12:20:17
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
long long n,k,p,j,a[400005],poz[400005],wpoz[400005],b[400005],x,c,m,R,L,i,w[400005],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];
     }
}

m=-33333;

    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;
}