Cod sursa(job #647595)

Utilizator rendorzegAndrei Pavel rendorzeg Data 11 decembrie 2011 17:18:35
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<fstream.h>
#define MAXN 200001
using namespace std;
ifstream f ("buline.in");
ofstream g ("buline.out");
struct sume{
	int s,p;
};
int n,p,l,maxim=0,v[MAXN],s[MAXN];
sume t[MAXN];

void init(){
	int i,tip;
	f>>v[1]>>tip;
	if (tip==0)
		v[1]*=(-1);
	s[1]=v[1];
	t[1].s=v[1];
	t[1].p=1;
	for (i=2;i<=n;i++){
		f>>v[i]>>tip;
		if (tip==0)
			v[i]*=(-1);
		s[i]=s[i-1]+v[i];
		if (s[i]>t[i-1].s){
			t[i].s=s[i];
			t[i].p=i;
		}
		else{
			t[i].s=t[i-1].s;
			t[i].p=t[i-1].p;
		}
	}
}

void sum1(){
	int sc=0,i,poz=1;
	for (i=1;i<n;i++){
		sc+=v[i];
		if (sc > maxim){
			maxim=sc;
			p=poz;
			l=i-poz+1;
		}
		if (sc<0){
			poz=i+1;
			sc=0;
		}
	}
}
void sum2(){
	int i,x;
	for (i=1;i<=n;i++)
	{
		x=t[i-1].s+s[n]-s[i-1];
		if (maxim<x){
			maxim=x;
			p=i;
			l=n-i+1+t[i-1].p;
		}
	}
}
int main(){
	init();
	sum1();
	sum2();
	g<<maxim<<" "<<p<<" "<<l;
	return 0;
}