Cod sursa(job #572324)

Utilizator TeodoraTanaseTeodora Tanase TeodoraTanase Data 5 aprilie 2011 11:01:50
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>

using namespace std;

const int M=200002;
int n, a[2*M], s[2*M], p[2*M], l[2*M];

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];
    }
    for (int i=n; i<2*n-1; i++)
        a[i]=a[i-n];
}

void secventa()
{
    s[0]=a[0]; l[0]=1; p[0]=0;
    for (int i=1; i<2*n-1; i++)
    {
        if (a[i]<=s[i-1]+a[i])
        {
            s[i]=s[i-1]+a[i];
            l[i]=l[i-1]+1;
            p[i]=p[i-1];
        }
        else
        {
            s[i]=a[i];
            l[i]=1;
            p[i]=i;
        }
    }
}

void afisare()
{
    int smax=-10001, poz=-1, lg=0;
    for (int i=0; i<2*n-1; i++)
        if (s[i]>smax && l[i]<n)
        {
            smax=s[i];
            poz=p[i];
            lg=l[i];
        }
    printf ("%d %d %d\n",smax,poz+1,lg);
}

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