Cod sursa(job #1802369)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 10 noiembrie 2016 10:43:54
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <cstdio>

using namespace std;
int v[200001],w[200001];
int main()
{
    FILE *fin=fopen ("buline.in","r");
    FILE *fout=fopen ("buline.out","w");
    int n,maxs,p,l,sum,i,pi,aux,x,semn;
    fscanf (fin,"%d",&n);
    maxs=p=l=-2000000000;
    sum=0;
    for (i=1;i<=n;i++){
        fscanf (fin,"%d%d",&x,&semn);
        if (!semn)
            v[i]=-x;
        else v[i]=x;
        sum+=v[i];
    }
    pi=1;
    for (i=1;i<=n;i++){
        if (w[i-1]+v[i]>v[i])
            w[i]=w[i-1]+v[i];
        else {
            w[i]=v[i];
            pi=i;
        }
        if (maxs<w[i]){
            maxs=w[i];
            p=pi;
            l=i-pi+1;
        }
        else if (maxs==w[i]){
            if (pi<p){
                p=pi;
                l=i-pi+1;
            }
            else if (p==pi && l>i-pi+1)
                l=i-pi+1;
        }
    }
    pi=1;
    for (i=1;i<=n;i++){
        if (w[i-1]+v[i]<v[i])
            w[i]=w[i-1]+v[i];
        else {
            w[i]=v[i];
            pi=i;
        }
        if (maxs<sum-w[i]){
            maxs=sum-w[i];
            p=(i+1)%n;
            if (!p)
                p=n;
            l=n-(i-pi+1);
        }
        else if (maxs==sum-w[i]){
            aux=(i+1%n);
            if (!aux)
                aux=n;
            if (aux<p){
                p=aux;
                l=n-(i-pi+1);
            }
            else if (p==aux && l>i-pi+1)
                l=n-(i-pi+1);
        }
    }
    fprintf (fout,"%d %d %d",maxs,p,l);
    return 0;
}