Pagini recente » Rating Gabi Ciornea (water_cooler) | Cod sursa (job #906726) | Monitorul de evaluare | Cod sursa (job #2175975) | Cod sursa (job #2116900)
#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.empty() && 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;
}