Cod sursa(job #2074715)

Utilizator IVVladIon Vlad Vasile IVVlad Data 24 noiembrie 2017 22:02:54
Problema Buline Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n,s[400000],v[200000],smax=-200000,ismin,ismax,t[400000],j[400000],da=0;
int main()
{
    bool x;
    f>>n;
    s[0]=0;
    for(int i=1; i<=n; i++)
    {
        f>>v[i];
        f>>x;
        if(x==0) v[i]=-v[i];
        s[i]=s[i-1]+v[i];
        if(t[i-1]<s[i])
        {
            t[i]=s[i];
            j[i]=i;
        }
        else
        {
            t[i]=t[i-1];
            j[i]=j[i-1];
        }
    }

    for(int i=1; i<=n+1; i++)
    {
        if(smax<=t[i-1]+s[n]-s[i-1])
        {
            if(da==0)
            {
                ismax=n+j[i-1]-i+1;
                da=1;
            }
            smax=t[i-1]+s[n]-s[i-1];
            if(ismin<i)
            {
                ismin=i;
                if(ismax>n+j[i-1]-i+1) ismax=n+j[i-1]-i+1;
            }
        }
    }
    g<<smax<<" "<<ismin<<" "<<ismax;
    return 0;
}