Cod sursa(job #572770)

Utilizator bogfodorBogdan Fodor bogfodor Data 5 aprilie 2011 16:49:24
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>

using namespace std;

const int M=200002;
int n, a[M],p,smin,smax;

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

void secventa()
{
    int s=0,cnt=0,lg,poz;
    for(int i=0;i<n;i++)
    {
        p+=a[i];
        s+=a[i];
        if(s<0)
        {
            s=0;
            cnt=i+1;
        }
        else
            if(s>smax)
            {
                smax=s;
                poz=cnt;
                lg=i-cnt+1;
            }
    }
    for(int i=0;i<n;i++)
        a[i]=-a[i];
    s=0;
    cnt=0;
    int p=0,lung=1;
    for(int i=0;i<n;i++)
    {
        s+=a[i];
        if(s>0)
        {
            s=0;
            cnt=i;
        }
        else
            if(s<smin)
            {
                smin=s;
                p=cnt;
                lung=i-cnt+1;
            }
    }
    if(p+smin>smax)
    {
        smax=p+smin;
        poz=p+lung;
        lg=n-lung;
    }
    printf("%d %d %d",smax,poz,lung);
}

int main()
{
    freopen ("buline.in","r",stdin);
    freopen ("buline.out","w",stdout);
    citire();
    secventa();
    return 0;
}