|
|
back to boardTime 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. |
|
|