Cod sursa(job #1416187)

Utilizator felixiPuscasu Felix felixi Data 7 aprilie 2015 16:28:09
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>

#define inf 2000000001

using namespace std;

ifstream fin("buline.in");
ofstream fout("buline.out");

int a[200001],n,s,p1,p2,p,l1,l2,maxv,minv,currentmax,currentmin,wh;

int main()
{
    fin>>n;

    for (int i=1; i<=n; ++i)
    {
        fin>>a[i]>>wh;
        if (!wh)
            a[i] = -a[i];
        s += a[i];
    }

    maxv = -inf;
    currentmax=-inf;

    for (int i=1; i<=n; ++i)
    {
        if (currentmax < 0)
        {
            currentmax = a[i];
            p = i;
        }
        else
        {
            currentmax += a[i];
        }

        if (currentmax > maxv)
        {
            maxv = currentmax;
            p1 = p;
            l1 = i-p+1;
        }
    }

    minv = inf;
    currentmin = inf;

    for (int i=1; i<=n; ++i)
    {
        if (currentmin >= 0)
        {
            currentmin = a[i];
            p = i;
        }
        else currentmin += a[i];

        if (currentmin < minv)
        {
            minv = currentmin;
            p2 = i+1;
            if (i==n)
                p2 = 1;
            l2 = n-(i-p+1);
        }
    }

    if (maxv > s - minv || l2 == 0)
    {
        fout<<maxv<<" "<<p1<<" "<<l1;
    }
    else
    {
        fout<<s-minv<<" "<<p2<<" "<<l2;
    }

}