Pagini recente » Cod sursa (job #391115) | Cod sursa (job #2812372) | Cod sursa (job #1411983) | Borderou de evaluare (job #1567671) | Cod sursa (job #1608617)
#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;
}