Cod sursa(job #1486568)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 15 septembrie 2015 08:41:26
Problema Buline Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<stdio.h>
int n,i,a[200001],b,s[200001],t[200001],w=-200001,x,z,l,j,k,p,r,e;
int main() {
    freopen("buline.in","r",stdin),freopen("buline.out","w",stdout),scanf("%d",&n),t[0]=-200001;
    for(i=1;i<=n;i++) {
        scanf("%d%d",a+i,&b);
        if(!b)
            a[i]=-a[i];
        s[i]=a[i]+s[i-1],t[i]=s[i]>t[i-1]?s[i]:t[i-1];
    }
    for(i=1;i<2*n;i++) {
        if(p>r)
            p=r,e=i;
        r+=(i<=n?a[i]:a[i-n]);
        if(i-j<n&&w<r-p)
            w=r-p,k=i;
        if(e<=k)
            j=e;
    }
    for(l=j,j=1;j<=n;j++)
    if(t[j-1]+s[n]-s[j-1]>w)
        w=t[j-1]+s[n]-s[j-1],l=j;
    for(i=l;i<n+l;i++) {
        x++,z+=(i>n?a[i-n]:a[i]);
        if(z==w)
            break;
    }
    printf("%d %d %d",w,l,x);
}