Cod sursa(job #1608617)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 22 februarie 2016 11:11:44
Problema Buline Scor 100
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" );

typedef long long i64;

const int nmax = 200000;
const int inf = 1 << 30;
i64 v[ 2 * nmax + 1 ];

deque< int > d;

int main() {
    i64 n;
    fin >> n;
    for( int i = 1; i <= n; ++ i ) {
        i64 s, x;
        fin >> s >> x;
        if ( x == 0 ) {
            v[ i ] = v[ i + n ] = -s;
        } else {
            v[ i ] = v[ i + n ] = s;
        }
    }
    i64 sol = -inf;
    int p, l;

    d.push_back( 0 );
    for( int i = 1; i <= 2 * n; ++ i ) {
        v[ i ] += v[ i - 1 ];
        if ( v[ i ] - v[ d.front() ] > sol ) {
            sol = v[ i ] - v[ d.front() ];
            p = inf, l = inf;
        }
        if ( v[ i ] - v[ d.front() ] == sol ) {
            if ( d.front() + 1 < p ) {
                p = d.front() + 1;
                l = i - d.front();
            } else if ( d.front() + 1 == p && i - d.front() < l ) {
                l = i - d.front();
            }
        }

        while ( !d.empty() && v[ d.back() ] > v[ i ] ) {
            d.pop_back();
        }
        d.push_back( i );
        if ( n < i + 1 - d.front() ) {
            d.pop_front();
        }
    }
    fout << sol << " " << p << " " << l << "\n";
    fin.close();
    fout.close();
    return 0;
}