Cod sursa(job #1130461)

Utilizator Toast97Calin Farcas Toast97 Data 28 februarie 2014 13:23:26
Problema Subsecventa de suma maxima Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

ifstream f("expresie2.in");
ofstream g("expresie2.out");

char e[100005];
int E[100005];
int v[100005];

const int MAX=100000;
const int DEL=666666;

int evaluare1(int poz);
int evaluare2(int poz);

int evaluare1(int poz)
{
    int i, p=0;

    for(i=poz-1;E[i]!=MAX+1;i--) {

      if(E[i]!=DEL) v[++p]=E[i];

      E[i]=DEL;
    }

    E[i]=DEL;

    int smax=-999999, sa=-1;

    for(i=1;i<=p;i++) {

    if(sa<0) sa=v[i];
    else sa+=v[i];

    if(sa>smax) smax=sa;

    }

    return smax;
}

int evaluare2(int poz)
{
    int i, p=0;

    for(i=poz-1;E[i]!=MAX+3;i--)  {

      if(E[i]!=DEL) v[++p]=E[i];

      E[i]=DEL;
    }

    E[i]=DEL;

    nth_element(v+1, v+((p+1)/2), v+p+1);

    return v[(p+1)/2];
}

int main()
{
    int i, sol=0, p=0, knr=0;

    f.getline(e,100001);

    int l=strlen(e);

    for(i=0;i<l;i++)  {

     if(e[i]=='(') E[++p]=MAX+1;
     else if(e[i]==')') E[++p]=evaluare1(p);
     else if(e[i]=='[') E[++p]=MAX+3;
     else if(e[i]==']') E[++p]=evaluare2(p);

     else if(e[i]=='-')  {

      int nr=0;

      i++;

      nr+=e[i]-48;

      if(e[i+1]-48>=0 && e[i+1]-48<=9) {

       nr*=10;
       i++;

       nr+=e[i]-48;

      }

      E[++p]=-nr, knr++;

     }

     else if(e[i]-48>=0 && e[i]-48<=9) {

       int nr=0;

       nr+=e[i]-48;

     if(e[i+1]-48>=0 && e[i+1]-48<=9) {

       nr*=10;
       i++;

       nr+=e[i]-48;

      }

      E[++p]=nr, knr++;

     }

    }

    for(i=1;i<=p;i++) if(E[i]!=DEL) sol+=E[i];

    g<<knr<<"\n"<<sol<<" ";

    f.close();
    g.close();
    return 0;
}