Time limit Exceed on 20 test. Why?

How to do my program more simply? Who khow?

When I send this program - Time limit Exceed on 20 test.

Help, who can!

Program zadacha;

var a:array[1..10000] of integer; b,c,i,j,n:integer; d:array[0..100000] of longint; m:longint;

begin

readln(n);

for i:=1 to n do

read(a[i]);

readln(m);

for i:=1 to m do begin

read(b,c);

for j:=b to c do

d[i]:=d[i]+a[j];

end;

for i:=1 to m do

writeln(d[i]);

end.

Re: Time limit Exceed on 20 test. Why?

100.000 * 10.000 = 1.000.000.000

change algoritm (he easy)

Re: Time limit Exceed on 20 test. Why?

100.000 * 10.000 = 1.000.000.000

change algoritm (he easy)

So, what algoritm must I use there? Can you tell me?

S[i..j] = S[1..j] - S[1..i-1] (-)

Re: S[i..j] = S[1..j] - S[1..i-1] (-)

I don't understand. Please, write once again.

see+++++++++++++

6

4

2

3

1

5

7

2

2 4

3 5 {k,n}

answer:

(4+2+3+1)-(4)=6

(4+2+3+1+5)-(4+2)=9

Clearly: a[n]-a[k-1]

Re: S[i..j] = S[1..j] - S[1..i-1] (-)

Posted by

Ikrom 7 May 2008 18:51

Thank you very much.

Re: see+++++++++++++

Posted by

yzlhm 9 Feb 2009 08:28

that is to amazing

Re: S[i..j] = S[1..j] - S[1..i-1] (-)

I don't see if it works faster than summing from i to j directly. Summing from 1 to j requires more work and then we yet have to compute another sum and subtract.