Cod sursa(job #2470877)

Utilizator Diana_IonitaIonita Diana Diana_Ionita Data 9 octombrie 2019 20:32:00
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n,i,b,w,poz,pozm,lm,l,v[400002];
long long smax,sum,best[400002],a[400002];
int main()
{
    fin>>n;
    for(i=1; i<=n; i++)
    {
        fin>>w>>b;
        if(b==0)
        {
            v[i]=-w;

        }
        else v[i]=w;
        sum+=v[i];
    }
    smax=v[1];

    poz=1;
    l=1;

    for(i=1; i<=n; i++)
    {
        best[i]=v[i];
        if(best[i]<best[i-1]+v[i])
        {
            best[i]=best[i-1]+v[i];
            l++;
        }
        else
        {
            poz=i;
            l=1;
        }


        if(smax<best[i]) smax=best[i],pozm=poz,lm=l;
    }
    a[1]=v[1];

    for(i=2; i<=n; i++)
    {
        if(a[i-1]+v[i]<v[i]) a[i]=a[i-1]+v[i],l++;
        else
        {
            a[i]=v[i];
            l=1;
            poz=i;
        }
        if(sum-a[i]>smax)
        {
            smax=sum-a[i];
            if(i==n) pozm=1;
            else pozm=i+1;
            lm=n-l;
        }
    }
    fout<<smax<<" "<<pozm<<" "<<lm;

    return 0;
}