Edited by author 23.12.2006 13:14

I also have the same problem.
My algorithm runs in O(nk) time it will surely get TLE...
how to optimize it?

You can do it in O(n) with + and - long arithmetics

Still TLE#18. I do it in O(n) with + and - long arithmetics.
Help, please!
Should I do long arothmetic by 4 numbers?
Мне делать длинную арифметику по 4 знака?
Мені робити довгу арифметику по 4 знака?
:)

Edited by author 23.12.2006 14:42

I got accepted, you can do long arithmetic with 8 numbers.
By the way I don't think using 4 numbers (10000) as radix will TLE.

:)

Thanks, I have AC!
But a little question:
 In my first solution (with 1 number) I used
 array[1..10000][1..3200] of shortint;
 than, (with 2 numbers) - array[1..10000][1..1600] of integer;
Isn't it the same? But in the second case I got MLE!
Whats wrong? Is sizeof(integer)=sizeof(longint)?
Thanks.

That depends on certain compilers.
Some compilers will tend to have sizeof(shortint) = sizeof(integer) or sizeof(integer) = sizeof(longint)...
that's where the problem lies...:(

shortint lies in range -128..127, so sizeof(shortint)=1, while sizeof(integer)=sizeof(longint)=4. So, second array eats double amount of memory in comparison with first one.

integer lies in range -32768..32767.
It's 2 bytes.
Ans longint is in -2147483648..2147483647
It's 4 bytes.

Do you use TP?
FreePascal 32-bit compiler
Integer - 32 bit
Read FAQ for differences

I use FP.
I write a program

var t:integer;
begin
  t:=0;
  writeln(sizeof(t));
end.

It shows 2.

var t:longint;
begin
  t:=0;
  writeln(sizeof(t));
end.

Shows 4.

sizeof(Integer) depends on version of FPC

I use O(n) DP with long arithmetics on 9 digits. Because 2*a-b falls in range -1e+9 ... +2e+9 for every digit.

Just use prefix sums to optimise dp.

Edited by author 02.03.2016 13:39