Cod sursa(job #1409338)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 30 martie 2015 14:45:46
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <cstdio>

using namespace std;

const int nmax = 200000;

int a[2*nmax+5];

int main()
{
    freopen("buline.in", "r", stdin);
    freopen("buline.out", "w", stdout);
    int n;
    scanf("%d", &n);
    int sum = 0;
    for(int i=0; i<n; i++)
    {
        int x, type;
        scanf("%d%d", &x, &type);
        a[i] = x * (type>0 ? 1 : -1);
        sum+=a[i];
    }
    int st = 0;
    int s = a[0];
    int smax = a[0];
    int stmax = 0;
    int drmax = 0;
    for(int i=1; i<n; i++)
    {
        if(s < 0)
        {
            s = a[i];
            st = i;
        }
        else s += a[i];
        if(s > smax)
        {
            smax = s;
            stmax = st;
            drmax = i;
        }
    }
    st = 0;
    s = a[0];
    int smin = a[0];
    int stmin = 0;
    int drmin = 0;
    for(int i=1; i<n; i++)
    {
        if(s > 0)
        {
            s = a[i];
            st = i;
        }
        else s+=a[i];
        if(s < smin)
        {
            smin = s;
            stmin = st;
            drmin = i;
        }
    }
    int sans, stans, lgans;
    if(smax > sum - smin)
    {
        sans = smax;
        stans = stmax;
        lgans = drmax - stmax + 1;
    }
    else
    {
        sans = sum - smin;
        stans = (drmin+1)%n;
        lgans = n-(drmin - stmin + 1);
    }
    printf("%d %d %d", sans, stans+1, lgans);
    return 0;
}