提出 #8678173

---

ソースコード 拡げる

;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-swank (set-dispatch-macro-character
           ;; enclose the form with VALUES to avoid being captured by LOOP macro
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(declaim (ftype (function * (values (unsigned-byte 31) &optional)) read-fixnum/10))
(defun read-fixnum/10 (&optional (in *standard-input*))
  (declare #.OPT
           #-swank (sb-kernel:ansi-stream in))
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
    (let* ((result (loop (let ((byte (%read-byte)))
                           (when (<= 48 byte 57)
                             (return (- byte 48))))))
           (prev-result 0))
      (declare ((unsigned-byte 31) result prev-result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq prev-result result
                    result (+ (- byte 48)
                              (* 10 result)))
              (return prev-result)))))))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;;;
;;; Body
;;;

(defconstant +inf+ #x7fffffff)

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (d (read))
         (dp (make-array (+ d 1) :element-type 'uint31 :initial-element 0))
         (costs/10 (make-array '(365 3000) :element-type 'uint31))
         (tmp-table (make-array n :element-type 'uint31)))
    (declare (uint16 d n))
    (dotimes (i d)
      (dotimes (j n)
        (let ((c (read-fixnum/10)))
          (setf (aref costs/10 i j) c))))
    (loop
      for x from 1 to d
      for new-value of-type uint31 = +inf+
      do (loop for k from 1 to x
               for min-delta of-type uint31 = +inf+
               for base-idx = (array-row-major-index costs/10 (- x k) 0)
               do (cond ((= k 1)
                         (dotimes (y n)
                           (let ((delta (* 10 (row-major-aref costs/10 (+ base-idx y)))))
                             (setf (aref tmp-table y) delta
                                   min-delta (min min-delta delta)))))
                        ((= k 2)
                         (dotimes (y n)
                           (let ((delta (+ (* 10 (row-major-aref costs/10 (+ base-idx y)))
                                           (* 9 (row-major-aref costs/10 (+ base-idx y 3000))))))
                             (setf (aref tmp-table y) delta
                                   min-delta (min min-delta delta)))))
                        ((>= k 3)
                         (dotimes (y n)
                           (let ((delta (+ (- (* 10 (row-major-aref costs/10 (+ base-idx y)))
                                              (row-major-aref costs/10 (+ base-idx y 3000))
                                              (* 2 (row-major-aref costs/10 (+ base-idx y 6000))))
                                           (aref tmp-table y))))
                             (setf (aref tmp-table y) delta
                                   min-delta (min min-delta delta))))))
                  (setq new-value
                        (min new-value (+ (aref dp (- x k)) min-delta))))
         (setf (aref dp x) new-value))
    (println (aref dp d))))

#-swank (main)

提出情報

ジャッジ結果