Cod sursa(job #2548462)

Utilizator mihnea03Ciocioiu Mihnea mihnea03 Data 16 februarie 2020 18:19:33
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <climits>
#define dim 200010
using namespace std;
int a[2*dim];
int s[2*dim];
int d[2*dim];
int i,n,p,u,x,Max,pr,l;

int main() {
    ifstream fin("buline.in");
    ofstream fout("buline.out");
    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>a[i]>>x;
        if (x==0) a[i]=-a[i];
        a[n+i]=a[i];
    }
    for (i=1;i<=2*n;i++) {
        s[i]=a[i]+s[i-1];
    }
    Max=-INT_MIN;
    p=1;
    ///fac un deque cu indicii la care incep sexventele de lungime maxima
    ///fiecare element poate ori sa fie adaugat la o secventa anterioara oria
    for (i=1;i<=2*n;i++) {
        while (p<=u&&s[i]<s[d[u]]) u--;
        d[++u]=i;
        if (i-d[p]+1==n+1) p++;
        if (s[i]-s[d[p]]>Max) {
            Max=s[i]-s[d[p]];
            pr=d[p]+1;
            l=i-d[p];
        }
    }
    fout<<Max<<" "<<pr<<" "<<l;
    return 0;
}