Cod sursa(job #843886)

Utilizator ericptsStavarache Petru Eric ericpts Data 28 decembrie 2012 16:09:41
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <cstdio>
using namespace std;

const int maxn = 200002;

int v[maxn];
long long S = 0;
int main()
{
    int n,i;
    int cr_max,cr_high_start,cr_high_end;
    int cr_min,cr_low_start,cr_low_end;
    int show_max,show_high_start,show_high_end;
    int show_min,show_low_start,show_low_end;
    bool semn;
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    scanf("%d\n",&n);
    const int N = n;
    i = 1;
    while(i<=N)
    {
        semn = 0;
        scanf("%d %d",&v[i],&semn);
        if(!semn)
            v[i]= -v[i] ;
        S+=v[i];
        i ++;
    }
    cr_max = -(1<<30);
    cr_min = 1<<30;
    show_max = cr_max;
    show_min = cr_min;
    for(i=1;i<=N;++i)
    {
        if(cr_max >= 0)
        {
            cr_max += v[i];
            cr_high_end = i;
        }
        else
        {
            cr_max = v[i];
            cr_high_start = i;
            cr_high_end = i;
        }
        if(cr_max > show_max)
        {
            show_max = cr_max;
            show_high_start = cr_high_start;
            show_high_end = cr_high_end;
        }



        if(cr_min <= 0)
        {
            cr_min += v[i];
            cr_low_end = i;
        }
        else
        {
            cr_min = v[i];
            cr_low_start=i;
            cr_low_end=i;
        }
        if(cr_min <  show_min)
        {
            show_min = cr_min;
            show_low_end = cr_low_end;
            show_low_start = cr_low_start;
        }
    }
    if(S-show_min > show_max)
    {
        show_max = S-show_min;
        show_high_start = show_low_end+1;
        show_high_end = show_low_start + N - show_low_end-1;
    }
    else
    {
        show_high_end -= show_high_start;
        ++show_high_end;
    }
    printf("%d %d %d\n",show_max,show_high_start,show_high_end);
    return 0;
}