Cod sursa(job #2117652)

Utilizator barbuionBarbu Ion barbuion Data 29 ianuarie 2018 08:13:25
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include<fstream>

using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int S[400005], N, a, b, Max, P, L,st,dr,p,l;
int q[400005];
int main(){
    fin >> N;
    for( int i = 1; i <= N; i++ ){
        fin >> a >> b;
        if(b==0)
           a=-a;
        S[i] = S[i + N] = a;
    }
    for( int i = 1; i <= 2 * N; i++ )
        S[i] += S[i - 1];
    st=1;dr=0;
    for(i=1;i<=2*n;i++)
    {
        while(st<=dr&&S[i]<=S[q[dr])
           dr--;
        q[++dr]=i;
        while(st<=dr&&i-q[st]>n)
           st++;
        if(S[i]-S[q[st]]>Max){
           Max=S[i]-S[q[st]];
           p=q[st]+1;
           l=i-p+1;
        }

    }
   fout<<Max<<" "<<p<<" "<<l;
    return 0;
}