Cod sursa(job #572795)

Utilizator TeodoraTanaseTeodora Tanase TeodoraTanase Data 5 aprilie 2011 17:07:45
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>

using namespace std;

const int M=200002;
int n, a[M], p, smax, smin, P, lg, s, S, poz, poz2, lg2;

void citire()
{
    scanf ("%d ",&n);
    for (int i=0; i<n; i++)
    {
        int x;
        scanf ("%d %d ",&a[i],&x);
        if (!x)
            a[i]=-a[i];
    }
}

void secventa()
{
    for (int i=0; i<n; i++)
    {
        P+=a[i];
        s+=a[i];
        if (s<0)
        {
            p=i+1;
            s=0;
        }
        else if (s>smax)
        {
            smax=s;
            poz=p;
            lg=i-p+1;
        }
    }
    for (int i=0; i<n; i++)
        a[i]=-a[i];
    s=p=0; smin=-M;
    for (int i=0; i<n; i++)
    {
        s+=a[i];
        if (s<0)
        {
            s=0;
            p=i+1;
        }
        else if (s>smin)
        {
            smin=s;
            poz2=p;
            lg2=i-p+1;
        }
    }
    if (P+smin>smax)
    {
        smax=P+smin;
        poz=poz2+lg2;
        lg=n-lg2;
    }
}

int main()
{
    freopen ("buline.in","r",stdin);
    freopen ("buline.out","w",stdout);
    citire();
    secventa();
    printf ("%d %d %d\n",smax,poz+1,lg);
    return 0;
}