1 / 1
Feb 2011

I have used a dp algo for spoj.pl/problems/LISA/1

//code goes as below.

I keep getting WA , while I have checked it with most of the test cases which I found in this forum.

e.g 1+0*0+2 ( 3 1)
1+3*3+0 ( 12 10)
1+3+3*0 ( 4 0)

#include <stdio.h>
#include <math.h>
#include <iostream>
#include<new>
#include<algorithm>
#include<vector>
#include<typeinfo>
#include<map>
#include <fstream>
#include "string.h"
#include<cstdio>
#include<functional>
#include<algorithm>
#include <cassert>
#include <cstdlib>
#include <limits.h>
unsigned long long int getOp(unsigned long long int a , char b ,unsigned long long int c)
{
	unsigned long long int  r = 0;
    if( b == '*')
	r = a * c;
else
	r = a+c;
return r;
}
int myatoi(char ch)
{
	int r = ch - '0';
	return r;
}
int main()
{
int test;
	scanf("%d",&test);
    char *input_g[5000];
for( int i = 0 ; i < test ; i++)
{
	char t[100];
	scanf("%s",&t);
	input_g[i] = (char *)malloc(strlen(t)+1);
	strcpy(input_g[i],t);
}

for( int i = 0 ; i < test ; i++)
{
	//op is operator array and num is number array
           //i.e if expression is 1+2*3+4 op = { +,* ,+} and num = {1,2,3,4}
           char op[50] , num[50];
	
	char input_l[100];

	strcpy(input_l,input_g[i]);
	//Array which stores max sum upto k elements;
           //i.e sum[k] would contain max possible sum found upto kth number
            unsigned long long int sum[50];
	unsigned long long int m_sum[50];
	
            char *p = &input_l[0];
	int indx1 = 0, indx2 = 0;
	for(; *p ;p++)
	{
 			if( *p == '*' || *p== '+' )
			{
				op[indx1] = *p;
				indx1++;
			}
			else
			{
				num[indx2] = *p;
				indx2++;
			}
		}
		op[indx1] = '\0';
		num[indx2] = '\0';
	  char ch  = op[0];
	  sum[0] = myatoi(num[0]);
	  m_sum[0] = myatoi(num[0]);
	  int l = strlen(num);
	  sum[1] = getOp(myatoi(num[0]),op[0],myatoi(num[1]));
	  m_sum[1] = getOp(myatoi(num[0]),op[0],myatoi(num[1]));	
         //simple dp loop.
	  for( int i = 2 ; i < l ; i++)
	  {
		 unsigned long long p = myatoi(num[i]);
		 unsigned long long int max = 0;
		 unsigned long long int min = ULLONG_MAX;
		unsigned long long int t = 0;
		unsigned long long int mt = 0;
    	for(int j = i ; j > 0 ; j--)
	{
		t = getOp(sum[j-1],op[j-1],p);
		mt = getOp(m_sum[j-1],op[j-1],p);
		if( t > max )
			max = t;
		if( mt < min )
			min = mt;
		p = getOp(myatoi(num[j-1]),op[j-1],p);
	}
	 sum[i] = max;
	 m_sum[i] = min;
  }

  printf("%llu %llu",sum[indx1],m_sum[indx1]);
      printf("\n");
}
 return 0;
}

Some one please help frowning

Suggested Topics

Topic Category Replies Views Activity
C and C++ 0 16 8d

Want to read more? Browse other topics in C and C++ or view latest topics.