Cod sursa(job #490453)

Utilizator S7012MYPetru Trimbitas S7012MY Data 6 octombrie 2010 16:51:31
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
/*
 * File:   main.cpp
 * Author: petru
 *
 * Created on 2010-10-06
 */


#include <fstream>
#include <deque>
#define deb(n) fprintf(stderr,"%d ",(n));
#define DN 200005
#define MULT 0x3f3f3f3f
#define LL long long
//#define int long long
using namespace std;

LL sir[DN*2],sol,st,lg;
int n;

int main()
{
	int i;
	ifstream f("buline.in");
	ofstream g("buline.out");
	f>>n;
	for(i=1; i<=n; ++i) {
	    int op;
	    f>>sir[i]>>op;
	    if(!op) sir[i]*=(-1);
	}
	for(i=n+1;i<n*2; ++i) sir[i]=sir[i-n];
	//n*=2;
    for(i=1;i<n*2; ++i) sir[i]+=sir[i-1];
    deque <int> d;
    for(i=1; i<n*2; ++i) {
        for(;!d.empty() && d.front()<=i-n;d.pop_front());
        for(;!d.empty() && sir[i]<sir[d.back()];d.pop_back());
        d.push_back(i);

        if(sir[i]-sir[d.front()]>sol) {
            sol=sir[i]-sir[d.front()];
            st=d.front()+1;
            lg=i-d.front();
        }
    }
    g<<sol<<' '<<st<<' '<<lg;
    f.close();
    g.close();
	return 0;
}