Cod sursa(job #1137781)

Utilizator BrandonChris Luntraru Brandon Data 9 martie 2014 13:59:28
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <cstdio>
using namespace std;
int v[400001];
int main()
{
    int n, i, asn, max = -2147483647, p, st, st2, dr, s, s0, theS = 0, l, l0, theL, dr0;
    bool var = 0;
    freopen("buline.in", "r", stdin);
    freopen("buline.out", "w", stdout);
    scanf("%d", &n);
    for(i = 1; i <= n; ++i)
    {
        scanf("%d%d", &v[i], &asn);
        if(asn == 0)
            v[i] = -v[i];
        v[n+i] = v[i];
        if(asn == 1)
            var = 1;
    }
    if(var == 0)
    {
        for(i = 1; i <= n; ++i)
            if(v[i] > max)
            {
                max = i;
                p = i;
            }
        printf("%d %d %d\n", max, p, 1);
    }
    else
    {
        n *= 2;
        for(st = 1; st <= n; ++st)
        {
            while(v[st] < 0)
                ++st;
            s = 0;
            l = 0;
            st2 = 2*st;
            dr = st;
            do
            {
                s += v[dr];
                ++l;
                ++dr;
            }while(dr < st2 && v[dr] > 0 && dr < n);
            s0 = 0;
            l0 = 0;
            dr0 = dr;
            label:
            while(v[dr0] < 0 && dr0 < n && dr0 < st2)
            {
                s0 += v[dr];
                ++l0;
                ++dr0;
            }
            //dr0 = dr;
            while(v[dr0] > 0 && dr0 < n && dr0 < st2)
            {
                s0 += v[dr0];
                ++l0;
                ++dr0;
            }
            if(s0 > 0)
            {
                l += l0;
                s += s0;
                dr = dr0;
                if(dr0 < st2)
                    goto label;
            }
            if(s > theS)
            {
                theS = s;
                theL = l;
                p = st;
            }
        }
    }
    printf("%d %d %d\n", theS, p, theL);
    return 0;
}