Cod sursa(job #72499)

Utilizator info_arrandrei gigea info_arr Data 14 iulie 2007 00:12:47
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>

using namespace std;

#define FIN "buline.in"
#define FOUT "buline.out"

int N,i,a[400005];
int S[200005];
int T[200005];
int sc,smax;
int in,out,ina,in1;
int leng;
int s1,s2;


int main()
{
    freopen(FIN,"r",stdin);
    freopen(FOUT,"w",stdout);
    
    scanf("%d",&N);
    for (i=1; i<=N; i++)
     {
      scanf("%d %d",&s1,&s2);
      if (s2==1) { a[i]=s1; a[i+N]=s1; }
       else  { a[i]=-s1; a[i+N]=-s1; }
     }
    S[1]=a[1]; T[1]=a[1]; int max=-100000;
    for (i=2; i<=N; i++)
    {
     S[i]=S[i-1]+a[i];
     if (S[i]>max) max=S[i];
     T[i]=max;
    } 
    max=-100000;
    for (i=1; i<=N; i++)
     if (T[i-1]+S[N]-S[i-1]>max) 
      { max=T[i-1]+S[N]-S[i-1]; in1=i; }
    sc=0;  
    for (i=in; i<=N*2; i++) 
     { sc+=a[i]; if (sc==max) break; }
             
    sc=smax=a[1];
    in = 1; out = 1;
    for (i=2; i<=N*2; i++)
    {
     if (sc<0 || i-ina>N)
      { sc=a[i]; ina=i; }  
     else sc+=a[i];
     if (sc>smax)
      { smax=sc; in=ina; out=i; }
    }
    if (smax>=max) printf("%d %d %d",smax,in,out-in+1);
//    else  
//     printf("%d %d %d",max,in1,i-in1+1);
    
    return 0;
}