Cod sursa(job #53075)

Utilizator raula_sanChis Raoul raula_san Data 20 aprilie 2007 20:56:18
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <cstdio>

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

#define dim 200001

int A[dim];
int P[dim];

int N;

long S[dim];
long T[dim];

long Max, St, 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);
}

void dynamics()
{
     long i;
     
     S[1] = A[1];
     T[1] = S[1];
     P[1] = 1;

     for(i=2; i<=N; ++i)
     {
              S[i] = S[i-1] + A[i];
              
              if(T[i-1] > S[i])
              {
                        T[i] = T[i-1];
                        P[i] = P[i-1];
              }
              
              else if(S[i] > T[i-1])
              {
                   T[i] = S[i];
                   P[i] = i;
              }
     }

     Max = S[N];
     St = 1;
     L = N;

     for(i=1; i<=N; ++i)
     {
              if(T[i-1] + S[N] - S[i] > Max)
              {
                        Max = T[i-1] + S[N] - S[i];
						St = i + 1;
						L = P[i-1] + N - i;
              }
     }
}

void print()
{
     freopen("buline.out", "w", stdout);

     if(St > N) St -= N;

	 printf("%ld %ld %ld", Max, St, L);
     
     fclose(stdout);
}