Poj Solution 1615

http://poj.org/problem?id=1615

#include"iostream"
#include"stdlib.h"
#include"memory.h"
//#include"time.h"
using namespace std;


long m[5][100],len[5],n,total,answer;


///////////////////////////
long cas;
///////////////////////////

void init()
{
    n=5;total=0;
    int i,j;
    for(i=0;i<n;i++)
    {
        len[i]=80;
        for(j=0;j<len[i];j++)
        {    
            m[i][j]=rand()%201-100;
            total+=m[i][j];
        }
    }
}


void init1()
{
    n=0;total=0;
    do
    {
        len[n]=0;
        do
        {
            cin>>m[n][len[n]++];
            total+=m[n][len[n]-1];
        }
        while(m[n][len[n]-1]!=9999&&m[n][len[n]-1]!=-9999);
    
        total-=m[n][len[n]-1];
        len[n]--;
        n++;
    }while(m[n-1][len[n-1]]!=-9999);

}

int a[5];long next;int prev[520];

void find(long sum,long max,int rest)
{
    int i;long sa,sb;
    
    if(answer>=0&&max>answer)return;

    if(rest==0)
    {
        answer=max;
        return;
    }

    for(i=0;i<n;i++)
    if(a[i]<len[i])
    {
        if(prev[rest]>=0&&prev[rest]!=i)
        {
            sa=m[prev[rest]][a[prev[rest]]-2];
            if(m[prev[rest]][a[prev[rest]]-1]+m[i][a[i]]>0)sa+=m[prev[rest]][a[prev[rest]]-1]+m[i][a[i]];

            sb=m[i][a[i]];
            if(m[i][a[i]+1]+m[prev[rest]][a[prev[rest]]-2]>0)sb+=m[i][a[i]+1]+m[prev[rest]][a[prev[rest]]-2];

            if(sa>sb)continue;
        }


        a[i]+=2;
        sum+=m[i][a[i]-2];
        prev[rest-2]=i;
        find(sum+m[i][a[i]-1],sum>max?sum:max,rest-2);
        sum-=m[i][a[i]-2];
        a[i]-=2;
    }
    return ;
}

void yasuo()
{
    int i,j,k;
    for(i=0;i<n;i++)
    {
        for(j=1,k=0;j<len[i];j++)
        {
            if(m[i][j]==0)continue;
            if((m[i][j]>=0&&m[i][k]>=0)||(m[i][j]<=0&&m[i][k]<=0))m[i][k]+=m[i][j];
            else 
            {
                k++;
                m[i][k]=m[i][j];
            }
        }
    
        len[i]=k+1;
        
        if(m[i][k]>0)m[i][len[i]++]=0;
        m[i][len[i]]=-9999;
    }
    return ;
}

int main()
{
    int t,i,st;long sum;
    cin>>t;
    while(t--)
    {
        init1();
        //init();

        yasuo();
    
        sum=0;st=0;
        for(i=0;i<n;i++)
        {
            a[i]=0;
            if(m[i][0]<=0)
            {
                a[i]++;
                sum+=m[i][0];
            }
            st+=len[i]-a[i];
        }
        answer=-1;prev[st]=-1;
        find(sum,0,st);
        
        cout<<answer<<endl;
    }
    return 0;
}