Cod sursa(job #1558895)

Utilizator aetherAlexandra Vanca aether Data 29 decembrie 2015 19:06:15
Problema Buline Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
# include <iostream>
# include <fstream>
# include <limits.h>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n, v[200010], sum[400020], deq[400020];
int main()
{
    int suma, Smaxi, mini, p, l, ramas, i, color,  prim, ulti;
    suma=mini=ramas=0;
    Smaxi=-INT_MAX;
    f>>n;
    for (i=1; i<=n; i++)
    {
        f>>v[i]>>color;
        if (color==0)
            v[i]=-v[i];
        v[n+i]=v[i];
        sum[i]=sum[i-1]+v[i];
    }
    for (i=n+1; i<=2*n; i++)
        sum[i]=sum[i-1]+v[i];

    prim=1;
    ulti=0;
    for (i=1; i<=2*n; i++)
    {
        while (sum[i]<=sum[deq[ulti]] && prim<=ulti)
        {
            ulti--;
        }
        deq[++ulti]=i;
        if (deq[prim]==i-n)     // dapasesc lungimea
            prim++;
        if (Smaxi<sum[i]-sum[deq[prim]])
        {
            Smaxi=sum[i]-sum[deq[prim]];
            p=deq[prim]+1;
            l=i-deq[prim];
        }

    }
    g<<Smaxi<<' '<<p<<' '<<l;

    return 0;
}