Cod sursa(job #393825)

Utilizator bora_marianBora marian bora_marian Data 9 februarie 2010 23:42:45
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<fstream>
using namespace std;
int v[400005];
int n,nr;
long long sol=-1000000;
//void SSm(int st,int dr);
void ssm();
//ofstream fout("buline.out");
int main()
{
    ifstream fin("buline.in");
    //freopen("buline.out","w",stdout);
    fin>>n;
    int i;
    for(i=1;i<=n;i++)
     {
         int a,b;
         fin>>a>>b;
         if(b==0)
          v[++nr]=-a;
         else
          v[++nr]=a;
    }
    for(i=1;i<n;i++)
       v[++nr]=v[i];
  ssm();
return 0;
}

void ssm ()
{
	int dq[200000], p[200000], st, dr;
	int scur, smin, x, y;
	scur=smin=v[1];
	x=y=1;
	st=dr=1;
	dq[st]=smin;
	p[st]=1;
	for (int i=2;i<2*n;i++)
	{
		scur+=v[i];
		if (scur-dq[st]>sol)
			sol=scur-dq[st], x=p[st], y=i;
		while (dr>=st && scur<dq[dr])dr--;
		dq[++dr]=scur, p[dr]=i;
		if (i-p[st]==n)
			st++;
	}
	ofstream fout ("buline.out");
	fout<<sol<<" "<<x+1<<" "<<y-x;
}