Cod sursa(job #2518764)

Utilizator tomaionutIDorando tomaionut Data 6 ianuarie 2020 16:14:51
Problema Buline Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n,s,smin,smax,stot,stmax,drmax,stmin,drmin;
int a[200005];
int main()
{
    int i,t,x,st;
    fin >> n;
    for (i=1; i<=n; i++)
    {
        fin >> x >> t;
        if (t==0) a[i]=-x;
        else a[i]=x;
        stot+=a[i];
    }
    smax=s=a[1];
    st=1;
    if (s<0) {s=0; st=2;}
    for (i=2; i<=n; i++)
    {
        s+=a[i];
        if (s>smax)
        {
            smax=s;
            stmax=st;
            drmax=i;
        }
        if (s<0)
        {
            s=0;
            st=i+1;
        }
    }

    smin=s=a[1];
    st=1;
    if (s>0) {s=0; st=2;}
    for (i=2; i<=n; i++)
    {
        s+=a[i];
        if (s<smin)
        {
            smin=s;
            stmin=st;
            drmin=i;
        }
        if (s>0)
        {
            s=0;st=i+1;
        }
    }

    stot-=smin;
    if (stot>smax)
    {
        fout << stot << " " << stmin+1 << " " << n-(drmin-stmin+1);
    }
    else if (stot>smax)
    {
        fout << smax << " " << stmax << " " << drmax-stmax+1;
    }
    else
    {
        fout << smax << " ";
        if (stmax<drmin+1)
            fout << stmax << " " << drmax-stmax+1;
        else fout << stot << " " << stmin+1 << " " << n-(drmin-stmin+1);
    }


    return 0;
}