Cod sursa(job #503681)

Utilizator andrei_stoicaStoica Andrei Florian andrei_stoica Data 24 noiembrie 2010 12:42:12
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
using namespace std;
ifstream in("buline.in");
ofstream out("buline.out"); 
//const int N=1<<18;
//const int INF =1<<30;
int v[200000];
int main()
{
    int i,sc,smax,stc,stmax,drmax,n,m,smin,stmin,drmin,s=0,max;
    sc=0;
    stc=1;
    smax=-2000000000;
	smin=2000000000;
    in>>n;
	for (i=0;i<n;i++)
	{
		in>>v[i]>>m;
		if (m==0)v[i]=-v[i];
		if(sc>0)       
		{
           sc=0;
           stc=i;
        }
        sc += v[i];
		s+=v[i];
		if(sc<smin)
        {
	    smin=sc;
		stmin=stc;
		drmin=i;
		}  
	}
	sc=0;
	for (i=0;i<n;i++)
	{
		if(sc<0)       
		{
           sc=0;
           stc=i;
        }
        sc += v[i];
		if(sc>smax)
		{
           smax=sc;
           stmax=stc;
           drmax=i;       
		}
	}
	sc=0;
	if (smax>s-smin)
	out<<smax<<" "<<stmax<<" "<<" "<<drmax-stmax+1;
	else
		out<<s-smin<<" "<<drmin+2<<" "<<n-drmin+stmin-1;

}