SPOJ DCEPC501 Solution

| July 01, 2015

The correct, optimal and working solution for programming question DCEPC501 on spoj

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>

#define DEBUG 1

using namespace std;

#define ll long long
#define gc getchar_unlocked

void scanint(ll int &x)
{
    register int c = getchar_unlocked();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}


int readline ( char * str ) {

	int i = 0;
	char ch;
	while ( (ch=getchar()) != '\n' ) {
		str[i++] = ch;
	}
	str[i] = '\0';
	return i;
}

ll int array[100010];
ll int mem[100010];

ll int max ( ll int a , ll int b ) {
	return a > b ? a : b;
}

ll int max3 ( ll int a , ll int b , ll int c ) {
	return max(a,max(b,c));
}

ll int f( int start , int end ) {

	if ( start >= end )
		return 0;

	if ( mem[start] != 0 )
		return mem[start];

	if ( start == end - 3 ) {
		mem[start] = array[start] + array[start+1] + array[start+2];
	}
	else if ( start == end - 2 ) {
		mem[start] = array[start] + array[start+1];
	}
	else if ( start == end - 1 ) {
		mem[start] = array[start];
	}	
	else {
		mem[start] = max3(
			f(start+2 , end) + array[start] , \
			f(start+4 , end) + array[start] + array[start+1], \
			f(start+6 , end) + array[start] + array[start+1] + array[start+2] \
	 	);
	}

	return mem[start];
}

int main ( int argc , char * argv[] ) {

	ll int t , z;
	scanf("%lld" , &t);
	for ( z = 1 ; z <= t ; z++ ) {

		for ( int i = 0 ; i < 100010 ; i++ )
			mem[i] = 0;

		ll int n;
		scanint(n);
		for ( int i = 0 ; i < n ; i++ ) {
			scanint(array[i]);
		}

		printf("%lld\n" , f(0,n));

	}
	return 0;
}