# PRLADDU -how do I not exceed the time limit?

Hello, this my first question here…

My program seems to work for all the test cases I make up, but for some reason it always exceeds the time limit. Here’s a link to my code: http://www.codechef.com/viewsolution/5201339

I can’t figure out how else to optimize my algorithm.
(I don’t know any set way to write pseudocode, but here’s an attempt)

``````int grass=0;//initial units of grass=0
Loop through array of villages D[] {
while (D[i]>=0) {
loop again through array of villages {
pick negative village j closest to the beginning
break;
}
increase negative number by one D[j]++
decrease positive number by one D[i]--
}
}
``````

How do I further reduce the time this takes to run?

This is what I did.
The Algorithm works in O(N) Time.

``````import java.util.*;
class DevuLand
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(--t>=0)
{
long grass=0,dnv=0;
int n=sc.nextInt();
long a[]=new long[n];
for(int i=0;i<n;i++)
{
a[i]=sc.nextLong();
}

for(int i=0;i<n;i++)
{
dnv+=a[i];
if(dnv>0)
grass+=dnv;
else
grass-=dnv;
}
System.out.println(grass);
}
}
}``````
3 Likes

This is what I did. Might not be the best way but still O(n). Since it is python, I don’t think explanation is needed. But sure you can ask if you have any doubt.

``````def solve():
#print "solving"
N = int(raw_input())
D = map(int, raw_input().split())
V = []
L = []
index = 0
cost = 0
while(D):
visit = D.pop(0)
if(visit > 0):
V.append((visit, index))
else:
L.append((abs(visit), index))
index += 1
#print V, L
while(V and L):
villagers, indexV = V.pop()
cost += villagers*abs(indexV-indexL)
else: