Cod sursa(job #286375)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 23 martie 2009 19:27:50
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
//#include<algorithm>
//using namespace std;
#include<stdio.h>

#define DIM 400001
#define INF -10001

int n,a[DIM/2],sum[DIM];

void solve(){
    int i,j,cul,st,dr,smax,min0,pozmin;

    scanf("%d",&n);
    for(i=1; i<=n; ++i){
        scanf("%d%d",&a[i],&cul);
        if(!cul)
            a[i]*=-1;}
    for(i=1; i<=2*n; ++i)
		sum[i]+=a[i<=n?i:i-n]+sum[i-1];
	for(i=1,smax=INF,min0=pozmin=0; i<=2*n; ++i){
		if(i-pozmin<=n&&sum[i]-min0>smax){
			smax=sum[i]-min0;
			st=pozmin;
			dr=i;}
		if(sum[i]<min0){
			min0=sum[i];
			pozmin=i+1;}
		if(i-pozmin>n){
			for(min0=sum[j=i-1]; j>=n-i; --j)
				if(sum[i]<min0){
					min0=sum[j];
					pozmin=j+1;}
			if(sum[i]-min0>smax){
				smax=sum[i]-min0;
				st=pozmin;
				dr=i;}}}
	printf("%d %d %d",smax,st,dr-st+1);}

int main(){
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    solve();
    return 0;}