Cod sursa(job #2413326)

Utilizator mihnea.anghelMihnea Anghel mihnea.anghel Data 23 aprilie 2019 12:12:23
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <fstream>

using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
long long n,i,x,val,maxi, v[500000], d[500000], start, durata, p, u;

int main()
{
	f>>n;
	for (i=1; i<=n; i++) {
		f>>x>>val;
		if (!val) x = -x;
		v[i] = v[i-1] + x;
		v[i+n]=x;
	}
	for (i=n+1; i <= 2*n; i++) v[i] += v[ i-1 ] ;
	p=1;
	d[++u]=0;
	for (i=1; i<=n*2; i++){
		while ( p<=u && v[i] < v[ d[u] ] ) u--;
		d[++u] = i;
		if ( i - d[p] - 1 == n ) p++;
		if ( v[i] - v[ d[p] ] > maxi){
			maxi = v[i] - v[ d[p] ];
			start = d[p];
			durata = i - start; 
		}
	} 
	g<< maxi <<" "<< start+1 <<" "<< durata ;
	return 0;
}