ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1330. Intervals

Time limit Exceed on 20 test. Why?
Posted by Crusader 3 Jun 2005 21:23
How to do my program more simply? Who khow?
When I send this program - Time limit Exceed on 20 test.
Help, who can!

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

for i:=1 to m do begin
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?
Posted by Виктор Крупко 3 Jun 2005 23:28
100.000 * 10.000 = 1.000.000.000
change algoritm (he easy)
Re: Time limit Exceed on 20 test. Why?
Posted by Crusader 4 Jun 2005 13:47
Виктор Крупко wrote 3 June 2005 23:28
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] (-)
Posted by Dmitry 'Diman_YES' Kovalioff 4 Jun 2005 19:47
Re: S[i..j] = S[1..j] - S[1..i-1] (-)
Posted by Crusader 7 Jun 2005 11:13
I don't understand. Please, write once again.
see+++++++++++++
Posted by Виктор Крупко 8 Jun 2005 01:10
6
4
2
3
1
5
7
2
2 4
3 5 {k,n}

(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] (-)
Posted by Googologist 4 Aug 2015 19:46
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.