Cod sursa(job #1557314)

Utilizator borcanirobertBorcani Robert borcanirobert Data 27 decembrie 2015 11:57:51
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <iostream>
#include <deque>
using namespace std;

ifstream fin("buline.in");
ofstream fout("buline.out");

const int MAXN = 400005;
int x, t;
int N;
int a[MAXN];
int maxim, p, l;
deque<int> Q;

void Read();
void Solve();

int main()
{
	Read();
	Solve();
	
	fin.close();
	fout.close();
	return 0;
}


void Read()
{
	int i;
	
	fin >> N;
	for ( i = 1; i <= N; i++ )
	{
		fin >> x >> t;
		if ( t == 0 ) x = -x;
		
		a[i] = a[i + N] = x;
	}
	
	for ( i = 1; i <= 2*N; i++ )
		a[i] = a[i - 1] + a[i];
}

void Solve()
{
	int i;
	
	for ( i = 1; i <= 2*N; i++ )
	{
		while ( !Q.empty() && a[Q.back()] >= a[i] )
			Q.pop_back();
		Q.push_back(i);
		
		if ( Q.front() == i - N )
			Q.pop_front();
		
		if ( maxim < a[i] - a[Q.front()] )
		{
			maxim = a[i] - a[Q.front()];
			p = Q.front() + 1;
			l = i - Q.front();
		}
	}
	
	fout << maxim << ' ' << p << ' ' << l << '\n';
}