Pagini recente » Cod sursa (job #1085840) | Statistici Alexandra Alexiu (transparentul) | Cod sursa (job #712926) | Cod sursa (job #2010773) | Cod sursa (job #1640428)
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int v[400010],i,j,n,m,ans,sum,l,r;
deque <int> d;
int main()
{
ans = -100000;
fin>>n;
for( i = 1 ; i <= n ; i++ )
{
fin>>v[ i ]>>l;
if( !l )
v[ i ] *= -1;
v[ i + n ] = v[ i ];
}
for( i = 1 ; i <= 2*n ; i++ )
v[ i ] += v[ i - 1 ];
d.push_back( 0 );
ans = -100000;
for( i = 1 ; i <= 2 * n ; i++ )
{
if( v[ i ] - v[ d.front() ] > ans )
{
ans = v[ i ] - v[ d.front() ];
l = d.front() + 1;
r = i-l+1;
}
while( d.size() && v[ d.back() ] >= v[ i ] )
d.pop_back();
d.push_back( i );
if( d.front() == i - n + 1 )
d.pop_front();
}
fout<<ans<<' '<<((l>n)?l-n:l)<<' '<<((r>n)?r-n:r);
return 0;
}