Cod sursa(job #290425)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 27 martie 2009 22:21:53
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<algorithm>
using namespace std;

#define DIM 200001
#define INF -1000001

int n,a[DIM];

void solve(){
    int i,c,st,nr,dr,smin,max0,max1,pozmax,pozmax1;

    scanf("%d",&n);
    for(i=1,max1=INF; i<=n; ++i){
        scanf("%d%d",&nr,&c);
        if(!c)
            nr*=-1;
        if(nr>max1){
            max1=nr;
            pozmax1=i;}
        a[i]=nr+a[i-1];}
    for(i=1,st=dr=-1,smin=0,max0=INF,pozmax=0; i<=n; ++i){
        if(a[i]-max0<smin){
            smin=a[i]-max0;
            st=pozmax;
            dr=i;}
        if(a[i]>max0){
            max0=a[i];
            pozmax=i+1;}}
    for(i=1; i<=n; ++i)
        if(a[i]>=0)
            i=n+1;
    if(i==n+1)
        printf("%d %d 1",max1,pozmax1);
    else{
        printf("%d ",a[n]-smin);
        if(!smin&&st==-1&&st==dr)
            printf("1 %d",n);
        else if(dr==n)
            printf("1 %d",n-dr+st-1);
        else
            printf("%d %d",dr+1,n-dr+st-1);}}

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