Cod sursa(job #882983)

Utilizator Theorytheo .c Theory Data 19 februarie 2013 17:09:00
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<fstream>
#include<queue>

using namespace std;

ifstream fin("buline.in");
ofstream fout("buline.out");

const int Nmax = 400009;

int N; int V[Nmax]; long long S[Nmax]; deque<int> Q;

void Read(){

    fin >>N;
    for(int i = 1; i <= N; ++i){
        int A, B; fin >>A >>B;

        if(B == 0) B = -1;

        V[i] = A * B;
    }
    for(int i = 1; i <= N; ++i)
        V[i + N] = V[i];

    for(int i = 1; i <= N + N; ++i)
        S[i] = S[i - 1] + V[i];
}

void Solve(){

    int Smax = (-1) * (1<<30);int PosMax = 0; int LenghtMax = 0; Q.push_back(0);

    for(int i = 1; i <= N + N ;++i){

        int Now = S[i] - S[Q.front()];
        int Pos = Q.front() + 1;
        int Lenght = i - Pos  + 1;

        if(Smax < Now ||(Smax == Now && Pos < PosMax ) ||(Smax == Now && Pos == PosMax && LenghtMax > Lenght))
            Smax = Now, PosMax = Pos, LenghtMax = Lenght;

        while(!Q.empty() && S[i] <= S[Q.back()])
            Q.pop_back();

        Q.push_back(i);

        if(i >= N + Q.front())
            Q.pop_front();
    }
    PosMax %= N + 1;
    fout << Smax <<" "<<PosMax <<" "<<LenghtMax;

}


int main(){

    Read(); Solve ();

    return 0;
}