Cod sursa(job #30367)

Utilizator RaduPRadu Padurean RaduP Data 13 martie 2007 20:30:12
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <cstdio>

#define inf 2000000001
#define Nmax 200005

int n, v[Nmax];
int best = -inf, start, lung;

void readdata()
{
    freopen("buline.in", "r", stdin);
    freopen("buline.out", "w", stdout);
    
    int i, val, semn;
    
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %d", &val, &semn);
        if (semn) v[i] = val;
        else v[i] = -val;
    }
}

void solve()
{
    int i, sum = 0, min = 0, poz = n+1, S = 0;
    int best2 = -inf, start2, lung2;
        
    //solutia nu este circulara    
    for (i = n; i; --i)
    {
        sum += v[i];
        if (sum - min >= best)
        {
            best = sum - min;
            start = i;
            lung = poz - i;
        }
        if (sum <= min)
        {
            min = sum;
            poz = i;
        }
    }
    
    //solutia este circulara
    for (i = 1; i <= n; ++i)
        S += v[i], v[i] = -v[i];
        
    min = 0, poz = 0;
    sum = 0;
    
    for (i = 1; i < n; ++i)
    {
        sum += v[i];
        if (sum - min > best2)
        {
            best2 = sum - min;
            start2 = i+1;
            lung2 = n - (i - poz);
        }
        if (sum < min)
        {
            min = sum;
            poz = i;
        }
    }
    
    best2 = S+best2;
    
    if ((best2 > best) || (best2 == best && start2 < start) || (best2 == best && start2 == start && lung2 < lung))
    {
        best = best2;
        start = start2;
        lung = lung2;
    }
    printf("%d %d %d\n", best, start, lung);
}

int main()
{
    readdata();
    solve();
    return 0;
}