Cod sursa(job #2865390)

Utilizator euyoTukanul euyo Data 8 martie 2022 19:45:53
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#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;
}