Cod sursa(job #72467)

Utilizator andrei_infoMirestean Andrei andrei_info Data 13 iulie 2007 22:14:04
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <stdio.h>
#include <stdlib.h>
#include <values.h>
#define max 200001
int n, a[max], s[max], t[max], tt[max];

void citire()
{
        freopen("buline.in","r",stdin);
        scanf("%d", &n);
        int aux;
        for (int i=1; i<=n; i++)
        {
                scanf("%d %d", &a[i], &aux);
                if (aux == 0) a[i]*=-1;
        }
        fclose(stdin);
}

inline int MAX( int a, int b)
{
        if (a>b) return a;
        else    return b;
}

void solve()
{
        t[1]=s[1]=a[1];

        for (int i = 2; i<=n; i++)
                s[i] =s[i-1] + a[i];

        tt[1]=1;
        for ( int i =2; i<=n; i++)
                {
                t[i] = MAX( t[i-1], s[i] );
                if (t[i] == t[i-1] ) tt[i] = tt[i-1];
                else tt[i] = i;
                }

        int rez=-MAXINT, pstart, lung;

        for (int i = 2; i<=n; i++)
        {
         //       rez = MAX ( t[i-1] + s[n]-s[i-1], rez);
         if (t[i-1] + s[n]-s[i-1] > rez )
         {
                rez = t[i-1] + s[n]-s[i-1];
                pstart = i;
                lung = n-i+1 + tt[i-1];
                //pstop = tt[i-1];
         }

        }

        int s=0,start=1;
        for (int i =1; i<=n; i++)
        {
                //s = MAX( s+a[i], a[i]);
                //rez = MAX( rez, s);
                if (s+a[i] > a[i])
                        s=s+a[i];
                else
                {
                        s=a[i];
                        start=i;
                }

                if (s> rez)
                {
                        rez=s; pstart=start; lung = i-start+1;
                }
        }
         
        freopen("buline.out", "w", stdout);
        printf("%d %d %d", rez, pstart, lung);
        fclose(stdout);
}
 
int main()
{
        citire();
        solve();

        return 0;
}