Cod sursa(job #1412208)

Utilizator VAIonescuIonescu Vlad-Andrei VAIonescu Data 1 aprilie 2015 10:27:43
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int nmax=200000;
int x[nmax+1];

int main()
{
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    int n,i,sc,smax,st,stm,drm,con,stm1,drm1,stot=0,l,l1,smin;
    scanf("%d",&n);
    for (i=0;i<n;++i){
        scanf("%d %d",&x[i],&con);
        if (!con){
            x[i]*=-1;
        }
        stot=stot+x[i];
    }
    sc=smax=x[0];
    st=stm=drm=0;
    l=1;
    for (i=1;i<n;++i,++l){
        if (sc+x[i]>x[i]){
            sc=sc+x[i];
        }
        else {
            sc=x[i];
            st=i;
            l=1;
        }
        if (sc>smax){
            stm=st;
            drm=i;
            smax=sc;
        }
    }
    sc=smin=x[0];
    st=stm1=drm1=0;
    l1=1;
    for (i=1;i<n;++i,++l1){
        if (sc+x[i]<x[i]){
            sc=sc+x[i];
        }
        else {
            sc=x[i];
            st=i;
            l1=1;
        }
        if (sc<smin){
            stm1=st;
            drm1=i;
            smin=sc;
        }
    }
    smin=stot-smin;
    if (smax>smin){
        printf("%d %d %d",smax,stm+1,l);
    }
    else if (smax==smin){
        if (stm<(drm1+1)%n){
            printf("%d %d %d",smax,stm+1,l);
        }
        else if ((drm1+1)%n<stm){
            printf("%d %d %d",smin,(drm1+1)%n+1,l1);
        }
        else{
            if (l<l1){
                printf("%d %d %d",smax,stm+1,l);
            }
            else{
                printf("%d %d %d",smin,(drm1+1)%n+1,l1);
            }
        }
    }
    else{
        printf("%d %d %d",smin,(drm1+1)%n+1,l1);
    }
    return 0;
}