Cod sursa(job #572809)

Utilizator Sm3USmeu Rares Sm3U Data 5 aprilie 2011 17:15:49
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <stdio.h>

using namespace std;

int a[200100];
int b;
int max=-12000;
int lungime;
int startfinal2;
int startfinal;
int lungime2;
int max2=-12000;
int n;
int suma;

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

void dinamica(int &max, int &startfinal, int &lungime)
{
    b=0;
    int start=0;
    for(int i=0;i<n;++i)
    {
        if(b+a[i]>=a[i])
            b+=a[i];
        else
        {
            b=a[i];
            start=i;
        }
        if(max<b)
        {
        //    if(i-start>=m)
      //          continue;
            max=b;
            lungime=i-start+1;
            startfinal=start;

        }
    }
}

void rez()
{
    int m=n;
    //n=n<<1;
    dinamica(max,startfinal,lungime);
    for(int i=0;i<n;i++)
    {
        a[i]=-a[i];
    }
    dinamica(max2,startfinal2,lungime2);
    if(suma+max2>max)
    {
        printf("%d %d %d",suma+max2,startfinal2+1+lungime2,n-lungime2);
    }
    else
        printf("%d %d %d",max,startfinal+1,lungime);
}

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