Cod sursa(job #2116895)

Utilizator robx12lnLinca Robert robx12ln Data 28 ianuarie 2018 12:06:09
Problema Buline Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<fstream>
#include<deque>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int S[400005], N, a, b, Smax, P, L;
deque<int> Dq;
int main(){
    fin >> N;
    for( int i = 1; i <= N; i++ ){
        fin >> a >> b;
        S[i] = S[i + N] = (b == 0) ? -a : a;
    }
    for( int i = 1; i <= 2 * N; i++ )
        S[i] += S[i - 1];
    Smax = S[1];
    P = L = 1;
    Dq.push_back( 1 );
    for( int i = 2; i <= 2 * N; i++ ){
        while( Dq.front() >= N )
            Dq.pop_front();
        if( Dq.empty() && i > N )
            break;
        while( !Dq.empty() && i - Dq.front() + 1 > N )
            Dq.pop_front();
        int pos = ( Dq.empty() ) ? 0 : Dq.front();
        if( Smax < S[i] - S[pos] ){
            Smax = S[i] - S[pos];
            P = pos + 1;
            L = i - pos;
        }else{
            if( Smax == S[i] - S[pos] )
                if( P > pos + 1 ){
                    P = pos + 1;
                    L = i - pos;
                }else
                    if( P == pos + 1 )
                        L = min( L, i - pos );
        }
        while( !Dq.empty() && S[ Dq.back() ] > S[i] )
            Dq.pop_back();
        Dq.push_back( i );
    }
    fout << Smax << " " << P << " " << L << "\n";
    return 0;
}