Cod sursa(job #53046)

Utilizator raula_sanChis Raoul raula_san Data 20 aprilie 2007 19:08:28
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>

void get_data();
void dynamics();
void print();

#define dim 200001

int A[dim];
int N;

long S;
long P, L;

int main()
{
    get_data();
    dynamics();
    print();
    
    return 0;
}

void get_data()
{
     freopen("buline.in", "r", stdin);
     
     long i;
     int code;
     
     for(scanf("%d", &N), i=1; i<=N; ++i)
     {
                      scanf("%d %d", A+i, &code);
                      A[i] *= !code ? -1 : 1;
     }
     
     fclose(stdin);
}

#define ind(i) (i) <= (N) ? (i) : (i-N);

void dynamics()
{
     long i;
     long j;
     long s, p, l;
     
     s = 0;
     p = 1;
     l = 0;

     S = A[1] - 1;
     
     for(i=1; i<=N<<1; ++i)
     {
              j = ind(i);
              s += A[j];
              ++ l;
              
              if(s > S)
              {
                   S = s;
                   P = p;
				   L = l;
              }
              
              if(s < 0)
              {
                   s = 0;
                   p = j + 1;
                   l = 0;
              }
              
              if(l == N)
              {
                   s -= A[p];
                   ++ p;
                   -- l;
              }
     }
}

void print()
{
     freopen("buline.out", "w", stdout);
     
     printf("%ld %ld %ld", S, P, L);
     
     fclose(stdout);
}