Cod sursa(job #1461864)

Utilizator cyg_Miky2003Dancaescu Mihai cyg_Miky2003 Data 16 iulie 2015 15:49:33
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>

using namespace std;
int x[200005];
int main() {
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    int n,i,ic,smax,sc,im,sfm,a,b,sfmin,imin,smax2,smin,stot=0;
    scanf("%d",&n);
    for(i=1; i<=n; ++i) {
        scanf("%d%d",&a,&b);
        if(b==0)
            b=-1;
        x[i]=a*b;
        stot+=x[i];
    }
    sc=smax=x[1];
    ic=im=sfm=1;
    for(i=2; i<=n; ++i) {
        if(sc+x[i]<=x[i])
            sc=x[i],
            ic=i;
        else sc+=x[i];
        if(sc>smax) {
            smax=sc;
            im=ic;
            sfm=i;
        }
    }
    sc=smin=x[1];
    ic=imin=sfmin=1;
    for(i=2; i<=n; ++i) {
        if(sc+x[i]>=x[i])
            sc=x[i],ic=i;
        else sc+=x[i];
        if(sc<smin) {
            smin=sc;
            imin=ic;
            sfmin=i;
        }
    }
    smax2=stot-smin;
    if(smax>=smax2)
        printf("%d %d %d",smax,im,sfm-im+1);
    else
        printf("%d %d %d",smax2,(sfmin+1)%n,n-(sfmin-imin+1));
    return 0;
}