Pagini recente » Cod sursa (job #2053486) | Cod sursa (job #2559151) | Cod sursa (job #807367) | Cod sursa (job #2219884) | Cod sursa (job #2569092)
#include <fstream>
#include <deque>
#define N 400001
using namespace std;
ifstream f ( "buline.in" );
ofstream g ( "buline.out" );
deque < int > dq;
int v[N];
int main()
{ int n, i, Max, sign, start, length;
f >> n;
for ( i = 1 ; i <= n; i++ ){
f >> v[i] >> sign;
if ( sign == 0 )
v[i] = -v[i];
}
for ( i = 1; i <= n; i++ )
v[i + n] = v[i];
for ( i = 1; i <= 2 * n; i++ )
v[i] += v[i - 1];
Max = v[1];
dq.push_back ( 1 );
for ( i = 2; i <= 2 * n; i++ ){
while ( !dq.empty ( ) && i - dq.front ( ) >= n )
dq.pop_front ( );
if ( Max < v[i] - v[dq.front ( )] ){
Max = v[i] - v[dq.front ( )];
start = dq.front ( ) + 1;
length = i - dq.front ( );
}
while ( !dq.empty ( ) && v[dq.back ( )] > v[i] )
dq.pop_back ( );
dq.push_back ( i );
}
g << Max << ' ' << start << ' ' << length;
}