Cod sursa(job #1093315)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 27 ianuarie 2014 21:43:00
Problema Buline Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<cstdio>

using namespace std;

int v[100010];

int n,i,a,b,s,begin,end,smax,inc,sf,beginf,endf,incf,sfmax,S;

int main() {

    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    scanf("%d",&n);

    for(i=1;i<=n;i++) {
        scanf("%d%d",&a,&b);
        if(b==0) b=-1;
        v[i]=a*b;
        S+=v[i];
    }

    s=smax=sf=sfmax=-(1<<31);
    for(i=1;i<=n;i++) {
        if(s<0)
            s=0,inc=i;
        if(sf<0)
            sf=0,incf=i;
        s+=v[i];
        sf+=v[i]*(-1);
        if(s>smax) {
            smax=s;
            begin=inc;
            end=i;
        }
        if(sf>sfmax) {
            sfmax=sf;
            beginf=incf;
            endf=i;
        }
    }

    sf=S+sfmax;
    if(sf>smax) {
        smax=sf;
        begin=endf+1;
        end=beginf-1+n;
    }

    printf("%d %d %d\n",smax,begin,end-begin+1);

    fclose(stdin);fclose(stdout);
    return 0;
}