Pagini recente » Cod sursa (job #2892619) | Cod sursa (job #2338824) | Cod sursa (job #2126054) | Cod sursa (job #3216347) | Cod sursa (job #2865390)
#include <fstream>
#include <deque>
using namespace std;
ifstream fin( "buline.in" );
ofstream fout( "buline.out" );
const int MAXN = 200005;
const int INF = 2e9 + 5;
int val[2 * MAXN];
int S[2 * MAXN];
deque<int> dq;
int res, st = INF, len = INF;
inline void upd( int _res, int _st, int _len ) {
if ( res < _res ) {
res = _res;
st = _st;
len = _len;
} else if ( res == _res && _st < st ) {
st = _st;
len = _len;
} else if ( res == _res && _st == st && _len < len ) {
len = _len;
}
}
void updDeq( int pos ) {
while ( dq.size() && S[pos] < S[dq.back()] ) {
dq.pop_back();
}
dq.push_back(pos);
}
int main() {
int n, x, y;
fin >> n;
for ( int i = 1; i <= n; ++i ) {
fin >> x >> y;
val[i + n] = val[i] = (y ? x : -x);
}
dq.push_back(0);
for ( int i = 1; i <= 2 * n; ++i ) {
S[i] = S[i-1] + val[i];
if ( i <= n ) {
upd( S[i] - S[dq.front()], dq.front() + 1, i - dq.front() );
updDeq( i );
}
}
for ( int i = n + 1; i <= 2 * n; ++i ) {
if ( dq.front() == i - n - 1 ) dq.pop_front();
upd( S[i] - S[dq.front()], dq.front() + 1, i - dq.front() );
updDeq( i );
}
fout << res << " " << st << " " << len;
fin.close();
fout.close();
return 0;
}