Cod sursa(job #2538257)

Utilizator NoemikulcsarKulcsar Noemi Noemikulcsar Data 4 februarie 2020 16:43:23
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
long long  n,i,b,l,lm,p,l1,lm2,p2,poz,poz2,smin,smax,suma,l2;
long long  best[200001],c[200001],a[200001];
int main()
{
    fin>>n;
    for(i=1; i<=n; i++)
    {
        fin>>a[i]>>b;
        if(b==0)a[i]=-a[i];
        suma+=a[i];

    }
    smin=10000;
    c[1]=a[1];
    best[1]=a[1];
    for(i=2; i<=n; i++)
    {
        if(best[i-1]+a[i]>=a[i]) best[i]=a[i]+best[i-1],l++;
        else
        {
            best[i]=a[i];
            p=i;
            l=1;
        }
        if(smax<best[i])
        {
            smax=best[i];
            poz=p;
            lm=l;
        }

        if(c[i-1]+a[i]<=a[i]) c[i]=c[i-1]+a[i],l2++;
        else
        {
            c[i]=a[i];
            p2=i;
            l2=1;
        }

        if(smin>c[i])
        {
            if(i==n)poz2=0;
            else poz2=i;
            smin=c[i];
            lm2=l2;

        }
    }
    if(suma-smin>smax)
    {
        fout<<suma-smin<<" "<<poz2+1<<" "<<n-lm2;
    }
    else if(suma-smin==smax)
    {
        if(poz2+1==poz) fout<<smax<<" "<<poz<<" "<<max(n-lm2,lm);
        else
        {
            if(poz2+1>poz)fout<<smax<<" "<<poz<<lm;
            else fout<<smax<<" "<<poz<<" "<<n-lm2;
        }
    }
    else  fout<<smax<<" "<<poz<<" "<<lm;
    return 0;
}