Cod sursa(job #2473950)

Utilizator Diana_IonitaIonita Diana Diana_Ionita Data 14 octombrie 2019 15:39:08
Problema Buline Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>

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

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