Cod sursa(job #2548030)

Utilizator teisanumihai84Mihai Teisanu teisanumihai84 Data 16 februarie 2020 08:45:16
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#define dim 200001
using namespace std;
int n, c, a[2*dim], i, s[2*dim], v[2*dim], pr, maxim, l, p, u;
int main()
{
    ifstream fin ("buline.in");
    ofstream fout ("buline.out");
    fin>>n;
    for (i=1; i<=n; i++)
    {
        fin>>a[i]>>c;
        if (c==0)
            a[i]=-a[i];
        a[n+i]=a[i];
        s[i]=s[i-1]+a[i];
    }
    for (i=1; i<=n; i++)
        s[n+i]=s[n+i-1]+a[n+i];
    p=1;
    u=0;
    maxim=-2000000000;
    for (i=1; i<=2*n; i++)
    {
        while (s[i]<=s[v[u]] && p<=u)
            u--;
        v[++u]=i;
        if (v[u]-v[p]==n)
            p++;
        if (s[i]-s[v[p]]>maxim)
        {
            maxim=s[i]-s[v[p]];
            pr=v[p]+1;
            l=i-v[p];
        }
    }
    fout<<maxim<<" "<<pr<<" "<<l;
}