module mod_dequeue_for_CHT
    implicit none
    type item_t
        !y=ax+b
        integer(16)::a
        integer(16)::b
    end type item_t

    type t_node
        type(item_t) :: item
        type(t_node), pointer :: prev => null()
        type(t_node), pointer :: next => null()
    end type t_node

    type t_dequeue
        integer :: num = 0
        type(t_node), pointer :: head => null()
        type(t_node), pointer :: tail => null()
    contains
    end type t_dequeue

contains

  function new_node(item) result(node)
    type(item_t), intent(in) :: item
    type(t_node), pointer :: node

    allocate(node)
    node%item = item
  end

subroutine pushback(this,item)
    class(t_dequeue), intent(inout) :: this
    type(item_t), intent(in) :: item
    type(t_node), pointer :: node
    node => new_node(item)
    if (associated(this%head)) then
      node%prev => this%tail
      this%tail%next => node
    else
      this%head => node
    end if
    this%tail => node
    this%num = this%num+1
end

subroutine pushfront(this,item)
    implicit none
    type(t_dequeue), intent(inout) :: this
    type(item_t), intent(in) :: item
    type(t_node), pointer :: node

    node => new_node(item)
    if (associated(this%tail)) then
      node%next => this%head
      this%head%prev => node
    else
      this%tail => node
    end if
    this%head => node
    this%num = this%num+1
    return
end subroutine

function poll_first(this) result(item)
    class(t_dequeue), intent(inout) :: this
    type(item_t) :: item
    item = this%head%item
end function

subroutine pop_first(this)
    class(t_dequeue), intent(inout) :: this
    type(t_node), pointer :: node
    node => this%head%next
    deallocate(this%head)
    this%head => node
    if (associated(node)) then
      node%prev => null()
    else
      this%tail => null()
    end if
    this%num = this%num-1
end

function poll_last(this) result(item)
    class(t_dequeue), intent(inout) :: this
    type(item_t) :: item
    item = this%tail%item
end function

subroutine pop_last(this)
    class(t_dequeue), intent(inout) :: this
    type(t_node), pointer :: node
    node => this%tail%prev
    deallocate(this%tail)
    this%tail => node
    if (associated(node)) then
      node%next => null()
    else
      this%head => null()
    end if
    this%num = this%num-1
end

integer function size_of(this)
    class(t_dequeue), intent(in) :: this
    size_of = this%num
end
end module mod_dequeue_for_CHT
module mod_CHT
    use mod_dequeue_for_CHT
contains
subroutine add_Line(this,a,b)
    type(t_dequeue)::this
    type(item_t)::item
    integer(16)::a,b
    item%a=a
    item%b=b
    if(size_of(this)>=2)then
        do while(Line_Check(this%tail%prev%item,this%tail%item,item))
            call pop_last(this)
            if(size_of(this)<2)exit
        end do
    end if
    call pushback(this,item)
end subroutine

logical function Line_Check(l1,l2,l3)
    type(item_t)::l1,l2,l3
    Line_Check= (l3%b - l2%b) * (l2%a - l1%a) >= (l2%b - l1%b) * (l3%a - l2%a)
end function

integer(16) function query_CHT(this,x)
    type(t_dequeue)::this
    integer(16)::x
    if(size_of(this) >= 2)then
        do while (size_of(this) >= 2 .and. line_x(poll_first(this),x)>=line_x(this%head%next%item,x))
            call pop_first(this)
            if(size_of(this)<2)exit
        end do
    endif
    query_CHT=line_x(poll_first(this),x)
end function

integer(16) function line_x(LINE,x)
    type(item_t)::Line
    integer(16)::x
    line_x=Line%a*x+line%b
end function
end module mod_CHT
program speedrun
   use mod_CHT
   integer(16)::N,C
   integer(16),allocatable,dimension(:)::H,dp
   type(t_dequeue)::CHT
   integer(16)::i
   read*,N,C
   allocate(H(N))
   allocate(DP(N))
   read*,H
   DP(1)=0_16
   do i=2,N
      call add_Line(CHT,-2_16*h(i-1),h(i-1)**2_16+DP(i-1))
      DP(i)=query_CHT(CHT,h(i))+H(i)**2_16+C
   end do
   print"(i0)",DP(N)
end program speedrun

Measured memory_bytes: 15360