Cod sursa(job #1540110)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 2 decembrie 2015 10:02:29
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include<iostream>
#include<fstream>
#define nmax 200005

using namespace std;

ifstream fin ("buline.in");
ofstream fout ("buline.out");

int smax, smin, stmin, stmax, drmin, drmax, n, S;
int a[nmax];

void Citire()
{
   int i, nr, semn;

   fin >> n; S = 0;
   
   for (i=1; i<=n; i++)
   {   
     fin >> nr >> semn;
     if (semn == 1) a[i] = nr;
     else a[i] = nr * (-1);
     S += a[i];
   }
}

void Ssmax()
{
    int i, s, st;
    smax = s = a[1];
    stmax = drmax = 1;
    st = 1;
    if (s > 0) {s = 0; st = 2;}
 
    for (i = 2; i <= n; i++)
    {
        s += a[i];
        if (s > smax)
        {
            smax = s; stmax = st; drmax = i;
        }
        if (s > 0)
        {
            s = 0; st = i + 1;
        }
    }
}


void Ssmin()      /// imi ramane in stmin, drmin si smin tot ce imi trebuie
{
    int i, s, st;
    smin = s = a[1];
    stmin = drmin = 1;
    st = 1;
    if (s > 0) {s = 0; st = 2;}
 
    for (i = 2; i <= n; i++)
    {
        s += a[i];
        if (s < smin)
        {
            smin = s; stmin = st; drmin = i;
        }
        if (s > 0)
        {
            s = 0; st = i + 1;
        }
    }
}

void Afisare()
{
     //// care este mai mare ?   
     //// S-ssmin sau smax?

     if (smax > S-smin)
     {
         fout << smax << " " << stmax << " " << drmax << endl;
     }
     else
     {
         /// incepe la sfarsitul secventei minime + 1 si se termina la inceputul secventei minime
         fout << S-smin << " " << (drmin + 1) << " " << (stmin + n - drmin - 1) << endl;
     }
}

int main ()
{
  Citire();
  Ssmax();
  Ssmin();
  Afisare();
  fout.close();
  fin.close();
  return 0;
}