The following appears fully optimizable using gcl 2.7.0 (cvs head).
Similar can be had in 2.6 with more declarations.
Take care,
=============================================================================
(deftype foo nil `(integer -1 10000))
(defstruct coin
(weight 1 :type foo)
(price 1 :type foo))
(defun solve2 (target-weight coins table)
(declare (foo target-weight))
(declare ((vector foo) table))
(declare (optimize (speed 3)))
(loop for i from 0 to target-weight do (setf (aref table i) -1))
(setf (aref table 0) 0)
(loop for c in coins do
(loop for i from (coin-weight c) to target-weight do
(let ((a (aref table (- i (coin-weight c)))))
(when (>= a 0)
(setf (aref table i)
(cond
((>= (aref table i) 0) (min (aref table i)
(+ a (coin-price c))))
(t (+ a (coin-price c)))))))))
(aref table target-weight))
(let ((table (make-array 10001 :element-type 'fixnum)))
(dotimes (i (read))
(let ((w (read)) (c nil) (r nil))
(setq w (- (read) w))
(dotimes (j (read))
(push (make-coin :weight (read) :price (read)) c))
(setq r (solve2 w c table))
(cond
(r (format t
"The minimum amount of money in the piggy-bank is ~a.~%" r))
(t (format t "This is impossible.~%"))))))
=============================================================================
"Anton V. Belyaev" <·············@gmail.com> writes:
> Rob,
>
> I tried GCL and recieved "Timelimit" also.
> I rewrote the program in C++ and it was accepted. It took 0.6 sec to
> complete the test.
> The time limit is 5 sec, so my Lisp program is at least 10 times slower
> than C++ one! :(
>
> The C++ variant is accepted, this means that asymptotically my
> algorithm is fast enougth.
> The case is low level optimization of Lisp program. Are there any
> resources on this?
>
--
Camm Maguire ····@enhanced.com
==========================================================================
"The earth is but one country, and mankind its citizens." -- Baha'u'llah