Hello All,

Recently I was faced with the following problem:

There are 'M' bulbs which are mounted on an X-axis (horizontal). Each bulb is attached to a switch (located at the same location on the X-axis), which can be used to turn the bulb OFF. The location of the switches are integers on the X-axis (L_i). A robot has been assigned the task to switch 'OFF' all the bulbs, which takes a unit amount of time to move a unit distance.

Given coordinates of 'M' bulbs (which are all in ON position initially) and a starting position 'S', the task is to switch off each one of them, such that the total power consumed is minimized. The power consumed by a bulb (in Watts) is equal to the time the bulb has remained 'ON'.

To illustrate with an example, suppose that there are 3 bulbs (A, B, C) located along the X-axis at coordinates 1, 3 and 5 respectively. If the starting position for the robot is 4, the minimal amount of power required to switch all the bulbs off would be 9.

Explanation:
The robot first switches off the bulb C, located at x=5. By the time it reaches 'C' (x=4 to x=5), 3 bulbs have been glowing for 1 second. Power consumption = 3 Watts. Next, the robot turns to the left and switches off bulb 'B'. It would take 2 seconds to reach 'B' from position 'C'. By that time 2 bulbs have been glowing. Power consumption = 4 Watts. The robot would further move to the left, and finally turn 'A' off, which would consume 2 more Watts. Hence, total power consumption = 3 + 4 + 2 = 9 Watts.

Constraints:
1 <= M <= 1000
1 <= L_i, S <= 1000000

My Solution:
I came up with the following dynamic programming formulation:

#include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <vector>

using namespace std;

/**
 *  dp[i][j][k] = Watts consumed when the bulbs from (i..j) exclusive have been switched off,
 *  		  where the current position of the robot is pos[k].
 */

int main()
{
	int T, S, N;
	cin >> T;
	while ( T-- )
	{
		cin >> N >> S;
		int pos[N+1];

		pos[0] = 0;
		for(int i=1; i<=N; i++)
		   cin >> pos[i];

		int dp[N+2][N+2][N+2];
		memset(dp, 0, sizeof(dp));

		for(int i=N; i>=0; i--)
		   for(int j=i-1; j>=0; j--)
		 	dp[0][i][j] = (N-i+1)*(pos[i] - pos[j]) + dp[0][i+1][i];

		for(int i=1; i<=N; i++)
		   for(int j=i+1; j<=N; j++)
			dp[i][N+1][j] = i*(pos[j] - pos[i]) + dp[i-1][N+1][i];

		for(int i=1; i<=N; i++)
		{
		   for(int j=N; j>i; j--)
		   {
		      for(int k=i+1; k<j; k++)
		      {
			   int left  = (N-j+i+1)*(pos[k] - pos[i]) + dp[i-1][j][i];
			   int right = (N-j+i+1)*(pos[j] - pos[k]) + dp[i][j+1][j];
			   dp[i][j][k] = min(left, right);
		      }
		   }
		}

		int curr = 0;
		while ( pos[curr] < S )
		   ++curr;

		if ( pos[curr] == S  )		cout << dp[0][2][1] + N*(pos[1] - S) << endl;
		else if ( S > pos[N] )		cout << dp[N-1][N+1][N] + N*(S - pos[N]) << endl;
		else if ( S == pos[curr] )	cout << dp[curr-1][curr+1][curr] << endl;
		else
		{
			cout << min( N*(pos[curr] - S  ) + dp[curr-1][curr+1][curr],
				     N*(S - pos[curr-1]) + dp[curr-2][curr][curr-1] )
			     << endl;
		}
	}
	return 0;
}

However, when I submitted this code to the judge, I got only 60/100. Can someone please tell me what is the problem with this code?

Thanks!