Cod sursa(job #2221950)

Utilizator patcasrarespatcas rares danut patcasrares Data 16 iulie 2018 10:56:39
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<fstream>
#include<algorithm>
#define DN 200005
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
long long n,s[DN],dp[DN],a[DN],f,rez,sum,poz,l,b[DN],c[DN];
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>a[i];
        fin>>f;
        if(f==0)
            a[i]=-a[i];
    }
    s[1]=dp[1]=a[1];
    b[1]=1;
    for(int i=2;i<=n;i++)
    {
        dp[i]=dp[i-1]+a[i];
        if(s[i-1]+a[i]>a[i])
        {
            s[i]=s[i-1]+a[i];
            b[i]=b[i-1];
        }
        else
        {
            s[i]=a[i];
            b[i]=i;
        }
        if(s[i]>rez)
        {
            rez=s[i];
            poz=b[i];
            l=i-b[i]+1;
        }
    }
    c[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(dp[i-1]>dp[i])
        {
            dp[i]=dp[i-1];
            c[i]=c[i-1];
        }
        else
            c[i]=i;
    }
    for(int i=n;i>1;i--)
    {
        sum+=a[i];
        if(sum+dp[i-1]>rez)
        {
            rez=sum+dp[i-1];
            l=c[i-1]+n-i+1;
            poz=i;
        }
    }
    fout<<rez<<' '<<poz<<' '<<l;
}