Cod sursa(job #1803973)

Utilizator RaduXD1Nicolae Radu RaduXD1 Data 12 noiembrie 2016 08:23:26
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>

using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int v[2000001],u[2000001],n,i,maxist,maxidr,minist,a,b,maxist1,maxidr1;
long long maxi,mini,s,maxi1;

int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>b>>a;
        if(a==1)
            v[i]=b;
        else
            v[i]=-b;
        u[i]=-v[i];
    }
    mini=0;
    minist=0;
    for(i=1;i<=n;i++)
    {
        v[i]+=v[i-1];
        if(mini>v[i-1])
        {
            mini=v[i-1];
            minist=i-1;
        }
        s=v[i]-mini;
        if(s>maxi)
        {
            maxi=s;
            maxist=minist+1;
            maxidr=i;
        }
    }
    mini=0;
    minist=0;
    for(i=1;i<=n;i++)
    {
        u[i]+=u[i-1];
        if(mini>u[i-1])
        {
            mini=u[i-1];
            minist=i-1;
        }
        s=u[i]-mini;
        if(s>maxi1)
        {
            maxi1=s;
            maxist1=minist+1;
            maxidr1=i;
        }
    }
    maxi1=-maxi1;
    if(maxi>=v[n]-maxi1)
        fout<<maxi<<" "<<maxist<<" "<<maxidr-maxist;
    else
        fout<<v[n]-maxi1<<" "<<maxidr1+1<<" "<<n-maxidr+maxist;
    fin.close();
    fout.close();
    return 0;
}