Cod sursa(job #214232)

Utilizator hadesgamesTache Alexandru hadesgames Data 13 octombrie 2008 15:42:21
Problema Buline Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <algorithm>
#include <utility>
#include <string>
#include <functional>
#include <sstream>
#include <fstream>
#include <iostream>
using namespace std;
#define FOR(i,a,b) for (i=a;i<=b;i++)
#define fori(it,v) for (it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fs first
#define ss second
#define all(c) c.begin(),c.end()
#define pf push_front
#define popb pop_back
#define popf pop_front
pair<int,int> secv[400005];
int a[400005];
int main()
{
	pair<int,pair<int,int> > minim;
	FILE *in,*out;
	int i,n;
	in=fopen ("buline.in","r");
	out=fopen("buline.out","w");
	fscanf(in,"%d",&n);
	int x;
	for(i=1;i<=n;i++)
	{
		fscanf(in,"%d%d",&a[i],&x);
		a[i+n]=a[i]=a[i]-2*a[i]*(!x);
		//printf("%d ",a[i]);
	}
	secv[1]=mp(a[1],1);
	minim=mp(a[1],mp(1,1));
	for (i=2;i<=n+n;i++)
	{
		while ((i-secv[i-1].ss+1>n||a[secv[i-1].ss]<0)&&secv[i-1].ss!=i)
		{
			secv[i-1].fs-=a[secv[i-1].ss];
			secv[i-1].ss++;
		}
		if (secv[i-1].fs+a[i]<=a[i])
			secv[i]=mp(a[i],i);
		else
			secv[i]=mp(secv[i-1].fs+a[i],secv[i-1].ss);
		minim=max(minim,mp(secv[i].fs,mp(secv[i].ss,i-secv[i].ss+1)));
	}
	fprintf(out,"%d %d %d\n",minim.fs,minim.ss.fs,minim.ss.ss);
	fclose(in);
	fclose(out);
	return 0;
}