結果
| 問題 |
No.2852 Yakitori Optimization Problem
|
| コンテスト | |
| ユーザー |
 osada-yum
|
| 提出日時 | 2024-09-02 16:13:56 |
| 言語 | Fortran (gFortran 14.2.0) |
| 結果 |
AC
|
| 実行時間 | 166 ms / 2,000 ms |
| コード長 | 21,939 bytes |
| コンパイル時間 | 2,545 ms |
| コンパイル使用メモリ | 44,672 KB |
| 実行使用メモリ | 10,640 KB |
| 最終ジャッジ日時 | 2024-09-02 16:14:03 |
| 合計ジャッジ時間 | 5,836 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 17 |
ソースコード
module merge_sort_m
use, intrinsic :: iso_fortran_env
implicit none
private
public :: merge_sort, merge_sort_descending
interface merge_sort
module procedure :: merge_sort_int32
module procedure :: merge_sort_with_key_int32
end interface merge_sort
interface merge_sort_descending
module procedure :: merge_sort_int32_descending
module procedure :: merge_sort_with_key_int32_descending
end interface merge_sort_descending
interface merge_sort
module procedure :: merge_sort_int64
module procedure :: merge_sort_with_key_int64
end interface merge_sort
interface merge_sort_descending
module procedure :: merge_sort_int64_descending
module procedure :: merge_sort_with_key_int64_descending
end interface merge_sort_descending
contains
!> merge_sort_int32: Sort arr(:) by sub function merge_sort_sub_int32.
!> arguments:
!> arr: array of some type.
subroutine merge_sort_int32(arr)
integer(int32), intent(inout) :: arr(:)
call merge_sort_sub_int32(arr, 1, size(arr))
end subroutine merge_sort_int32
!> merge: Algorithm for merge_sort, check if Left or Right is end in each loop.
!> arguments:
!> arr: array of some type, (out) arr(p:r) is sorted.
!> p, q, r: integer, indices p is start, r is end, q = floor( (p+q)/2 ).
!> variables:
!> Left, Right: array of typeof(arr), sorted
!> l_max, r_max: integer, max index of Left or Right.
subroutine merge_int32(arr, p, q, r)
integer(int32), intent(inout) :: arr(:)
integer(int32), intent(in) :: p, q, r
integer(int32) :: Left(1:q-p+1), Right(1:r-q)
integer(int32) :: l_max, r_max
l_max = q-p+1
r_max = r-q
block
!> i, j, k: integer, loop counters.
integer(int32) :: i, j, k
Left(1:l_max) = arr(p:q)
Right(1:r_max) = arr(q+1:r)
i = 1
j = 1
do k = p, r
if (Left(i) <= Right(j)) then
arr(k) = Left(i)
i = i + 1
if (i > l_max) then
arr(k+1:r) = Right(j:)
return
end if
else
arr(k) = Right(j)
j = j + 1
if (j > r_max) then
arr(k+1:r) = Left(i:)
return
end if
end if
end do
end block
end subroutine merge_int32
!> merge_sort_sub: Recursive function used by merge_sort.
!> arguments:
!> arr: array of some type.
!> p, r: integer, p is start of arr, r is end of arr.
!> variables:
!> q: integer, q = floor( (p+q)/2 )
recursive subroutine merge_sort_sub_int32(arr, p, r)
integer(int32), intent(inout) :: arr(:)
integer(int32), intent(in) :: p, r
integer(int32) :: q
if (p < r) then
q = (p+r)/2
call merge_sort_sub_int32(arr, p, q)
call merge_sort_sub_int32(arr, q+1, r)
call merge_int32(arr, p, q, r)
end if
end subroutine merge_sort_sub_int32
!> merge_sort_with_key_int32: Sort key(:) sub function merge_sort_sub_with_key_int32.
!> arguments:
!> key: array of some type.
!> indices: array of some type.
subroutine merge_sort_with_key_int32(key, indices)
integer(int32), intent(inout) :: key(:)
integer(int32), intent(inout) :: indices(:)
call merge_sort_sub_with_key_int32(key, indices, 1, size(key))
end subroutine merge_sort_with_key_int32
!> merge_with_key: Algorithm for merge_sort, check if Left or Right is end in each loop.
!> arguments:
!> indices: array of indices.
!> key: array of some type, (out) key(p:r) is sorted.
!> p, q, r: integer, indices p is start, r is end, q = floor( (p+q)/2 ).
!> variables:
!> Left, Right: array of typeof(indices), sorted
!> l_max, r_max: integer, max index of Left or Right.
subroutine merge_with_key_int32(key, indices, p, q, r)
integer(int32), intent(inout) :: key(:)
integer(int32), intent(inout) :: indices(:)
integer(int32), intent(in) :: p, q, r
integer(int32) :: Left(1:q-p+1), Right(1:r-q)
integer(int32) :: Left_key(1:q-p+1), Right_key(1:r-q)
integer(int32) :: l_max, r_max
l_max = q-p+1
r_max = r-q
block
!> i, j, k: integer, loop counters.
integer(int32) :: i, j, k
Left(1:l_max) = indices(p:q)
Right(1:r_max) = indices(q+1:r)
Left_key(1:l_max) = key(p:q)
Right_key(1:r_max) = key(q+1:r)
i = 1
j = 1
do k = p, r
if (Left_key(i) <= Right_key(j)) then
key(k) = Left_key(i)
indices(k) = Left(i)
i = i + 1
if (i > l_max) then
key(k+1:r) = Right_key(j:)
indices(k+1:r) = Right(j:)
return
end if
else
key(k) = Right_key(j)
indices(k) = Right(j)
j = j + 1
if (j > r_max) then
key(k+1:r) = Left_key(i:)
indices(k+1:r) = Left(i:)
return
end if
end if
end do
end block
end subroutine merge_with_key_int32
!> merge_sort_sub_with_key: Recursive function used by merge_sort_with_key.
!> arguments:
!> indices: array of indices.
!> key: array of some type.
!> p, r: integer, p is start of arr, r is end of arr.
!> variables:
!> q: integer, q = floor( (p+q)/2 )
recursive subroutine merge_sort_sub_with_key_int32(key, indices, p, r)
integer(int32), intent(inout) :: key(:)
integer(int32), intent(inout) :: indices(:)
integer(int32), intent(in) :: p, r
integer(int32) :: q
if (p < r) then
q = (p+r)/2
call merge_sort_sub_with_key_int32(key, indices, p, q)
call merge_sort_sub_with_key_int32(key, indices, q+1, r)
call merge_with_key_int32(key, indices, p, q, r)
end if
end subroutine merge_sort_sub_with_key_int32
!> merge_sort_int32_descending: Sort arr(:) by sub function merge_sort_sub_int32_descending.
!> arguments:
!> arr: array of some type.
subroutine merge_sort_int32_descending(arr)
integer(int32), intent(inout) :: arr(:)
call merge_sort_sub_int32_descending(arr, 1, size(arr))
end subroutine merge_sort_int32_descending
!> merge: Algorithm for merge_sort, check if Left or Right is end in each loop.
!> arguments:
!> arr: array of some type, (out) arr(p:r) is sorted.
!> p, q, r: integer, indices p is start, r is end, q = floor( (p+q)/2 ).
!> variables:
!> Left, Right: array of typeof(arr), sorted
!> l_max, r_max: integer, max index of Left or Right.
subroutine merge_int32_descending(arr, p, q, r)
integer(int32), intent(inout) :: arr(:)
integer(int32), intent(in) :: p, q, r
integer(int32) :: Left(1:q-p+1), Right(1:r-q)
integer(int32) :: l_max, r_max
l_max = q-p+1
r_max = r-q
block
!> i, j, k: integer, loop counters.
integer(int32) :: i, j, k
Left(1:l_max) = arr(p:q)
Right(1:r_max) = arr(q+1:r)
i = 1
j = 1
do k = p, r
if (Left(i) >= Right(j)) then
arr(k) = Left(i)
i = i + 1
if (i > l_max) then
arr(k+1:r) = Right(j:)
return
end if
else
arr(k) = Right(j)
j = j + 1
if (j > r_max) then
arr(k+1:r) = Left(i:)
return
end if
end if
end do
end block
end subroutine merge_int32_descending
!> merge_sort_sub: Recursive function used by merge_sort.
!> arguments:
!> arr: array of some type.
!> p, r: integer, p is start of arr, r is end of arr.
!> variables:
!> q: integer, q = floor( (p+q)/2 )
recursive subroutine merge_sort_sub_int32_descending(arr, p, r)
integer(int32), intent(inout) :: arr(:)
integer(int32), intent(in) :: p, r
integer(int32) :: q
if (p < r) then
q = (p+r)/2
call merge_sort_sub_int32_descending(arr, p, q)
call merge_sort_sub_int32_descending(arr, q+1, r)
call merge_int32_descending(arr, p, q, r)
end if
end subroutine merge_sort_sub_int32_descending
!> merge_sort_with_key_int32_descending: Sort key(:) sub function merge_sort_sub_with_key_int32_descending.
!> arguments:
!> key: array of some type.
!> indices: array of some type.
subroutine merge_sort_with_key_int32_descending(key, indices)
integer(int32), intent(inout) :: key(:)
integer(int32), intent(inout) :: indices(:)
call merge_sort_sub_with_key_int32_descending(key, indices, 1, size(key))
end subroutine merge_sort_with_key_int32_descending
!> merge_with_key: Algorithm for merge_sort, check if Left or Right is end in each loop.
!> arguments:
!> indices: array of indices.
!> key: array of some type, (out) key(p:r) is sorted.
!> p, q, r: integer, indices p is start, r is end, q = floor( (p+q)/2 ).
!> variables:
!> Left, Right: array of typeof(indices), sorted
!> l_max, r_max: integer, max index of Left or Right.
subroutine merge_with_key_int32_descending(key, indices, p, q, r)
integer(int32), intent(inout) :: key(:)
integer(int32), intent(inout) :: indices(:)
integer(int32), intent(in) :: p, q, r
integer(int32) :: Left(1:q-p+1), Right(1:r-q)
integer(int32) :: Left_key(1:q-p+1), Right_key(1:r-q)
integer(int32) :: l_max, r_max
l_max = q-p+1
r_max = r-q
block
!> i, j, k: integer, loop counters.
integer(int32) :: i, j, k
Left(1:l_max) = indices(p:q)
Right(1:r_max) = indices(q+1:r)
Left_key(1:l_max) = key(p:q)
Right_key(1:r_max) = key(q+1:r)
i = 1
j = 1
do k = p, r
if (Left_key(i) >= Right_key(j)) then
key(k) = Left_key(i)
indices(k) = Left(i)
i = i + 1
if (i > l_max) then
key(k+1:r) = Right_key(j:)
indices(k+1:r) = Right(j:)
return
end if
else
key(k) = Right_key(j)
indices(k) = Right(j)
j = j + 1
if (j > r_max) then
key(k+1:r) = Left_key(i:)
indices(k+1:r) = Left(i:)
return
end if
end if
end do
end block
end subroutine merge_with_key_int32_descending
!> merge_sort_sub_with_key: Recursive function used by merge_sort_with_key.
!> arguments:
!> indices: array of indices.
!> key: array of some type.
!> p, r: integer, p is start of arr, r is end of arr.
!> variables:
!> q: integer, q = floor( (p+q)/2 )
recursive subroutine merge_sort_sub_with_key_int32_descending(key, indices, p, r)
integer(int32), intent(inout) :: key(:)
integer(int32), intent(inout) :: indices(:)
integer(int32), intent(in) :: p, r
integer(int32) :: q
if (p < r) then
q = (p+r)/2
call merge_sort_sub_with_key_int32_descending(key, indices, p, q)
call merge_sort_sub_with_key_int32_descending(key, indices, q+1, r)
call merge_with_key_int32_descending(key, indices, p, q, r)
end if
end subroutine merge_sort_sub_with_key_int32_descending
!> merge_sort_int64: Sort arr(:) by sub function merge_sort_sub_int64.
!> arguments:
!> arr: array of some type.
subroutine merge_sort_int64(arr)
integer(int64), intent(inout) :: arr(:)
call merge_sort_sub_int64(arr, 1, size(arr))
end subroutine merge_sort_int64
!> merge: Algorithm for merge_sort, check if Left or Right is end in each loop.
!> arguments:
!> arr: array of some type, (out) arr(p:r) is sorted.
!> p, q, r: integer, indices p is start, r is end, q = floor( (p+q)/2 ).
!> variables:
!> Left, Right: array of typeof(arr), sorted
!> l_max, r_max: integer, max index of Left or Right.
subroutine merge_int64(arr, p, q, r)
integer(int64), intent(inout) :: arr(:)
integer(int32), intent(in) :: p, q, r
integer(int64) :: Left(1:q-p+1), Right(1:r-q)
integer(int32) :: l_max, r_max
l_max = q-p+1
r_max = r-q
block
!> i, j, k: integer, loop counters.
integer(int32) :: i, j, k
Left(1:l_max) = arr(p:q)
Right(1:r_max) = arr(q+1:r)
i = 1
j = 1
do k = p, r
if (Left(i) <= Right(j)) then
arr(k) = Left(i)
i = i + 1
if (i > l_max) then
arr(k+1:r) = Right(j:)
return
end if
else
arr(k) = Right(j)
j = j + 1
if (j > r_max) then
arr(k+1:r) = Left(i:)
return
end if
end if
end do
end block
end subroutine merge_int64
!> merge_sort_sub: Recursive function used by merge_sort.
!> arguments:
!> arr: array of some type.
!> p, r: integer, p is start of arr, r is end of arr.
!> variables:
!> q: integer, q = floor( (p+q)/2 )
recursive subroutine merge_sort_sub_int64(arr, p, r)
integer(int64), intent(inout) :: arr(:)
integer(int32), intent(in) :: p, r
integer(int32) :: q
if (p < r) then
q = (p+r)/2
call merge_sort_sub_int64(arr, p, q)
call merge_sort_sub_int64(arr, q+1, r)
call merge_int64(arr, p, q, r)
end if
end subroutine merge_sort_sub_int64
!> merge_sort_with_key_int64: Sort key(:) sub function merge_sort_sub_with_key_int64.
!> arguments:
!> key: array of some type.
!> indices: array of some type.
subroutine merge_sort_with_key_int64(key, indices)
integer(int64), intent(inout) :: key(:)
integer(int32), intent(inout) :: indices(:)
call merge_sort_sub_with_key_int64(key, indices, 1, size(key))
end subroutine merge_sort_with_key_int64
!> merge_with_key: Algorithm for merge_sort, check if Left or Right is end in each loop.
!> arguments:
!> indices: array of indices.
!> key: array of some type, (out) key(p:r) is sorted.
!> p, q, r: integer, indices p is start, r is end, q = floor( (p+q)/2 ).
!> variables:
!> Left, Right: array of typeof(indices), sorted
!> l_max, r_max: integer, max index of Left or Right.
subroutine merge_with_key_int64(key, indices, p, q, r)
integer(int64), intent(inout) :: key(:)
integer(int32), intent(inout) :: indices(:)
integer(int32), intent(in) :: p, q, r
integer(int32) :: Left(1:q-p+1), Right(1:r-q)
integer(int64) :: Left_key(1:q-p+1), Right_key(1:r-q)
integer(int32) :: l_max, r_max
l_max = q-p+1
r_max = r-q
block
!> i, j, k: integer, loop counters.
integer(int32) :: i, j, k
Left(1:l_max) = indices(p:q)
Right(1:r_max) = indices(q+1:r)
Left_key(1:l_max) = key(p:q)
Right_key(1:r_max) = key(q+1:r)
i = 1
j = 1
do k = p, r
if (Left_key(i) <= Right_key(j)) then
key(k) = Left_key(i)
indices(k) = Left(i)
i = i + 1
if (i > l_max) then
key(k+1:r) = Right_key(j:)
indices(k+1:r) = Right(j:)
return
end if
else
key(k) = Right_key(j)
indices(k) = Right(j)
j = j + 1
if (j > r_max) then
key(k+1:r) = Left_key(i:)
indices(k+1:r) = Left(i:)
return
end if
end if
end do
end block
end subroutine merge_with_key_int64
!> merge_sort_sub_with_key: Recursive function used by merge_sort_with_key.
!> arguments:
!> indices: array of indices.
!> key: array of some type.
!> p, r: integer, p is start of arr, r is end of arr.
!> variables:
!> q: integer, q = floor( (p+q)/2 )
recursive subroutine merge_sort_sub_with_key_int64(key, indices, p, r)
integer(int64), intent(inout) :: key(:)
integer(int32), intent(inout) :: indices(:)
integer(int32), intent(in) :: p, r
integer(int32) :: q
if (p < r) then
q = (p+r)/2
call merge_sort_sub_with_key_int64(key, indices, p, q)
call merge_sort_sub_with_key_int64(key, indices, q+1, r)
call merge_with_key_int64(key, indices, p, q, r)
end if
end subroutine merge_sort_sub_with_key_int64
!> merge_sort_int64_descending: Sort arr(:) by sub function merge_sort_sub_int64_descending.
!> arguments:
!> arr: array of some type.
subroutine merge_sort_int64_descending(arr)
integer(int64), intent(inout) :: arr(:)
call merge_sort_sub_int64_descending(arr, 1, size(arr))
end subroutine merge_sort_int64_descending
!> merge: Algorithm for merge_sort, check if Left or Right is end in each loop.
!> arguments:
!> arr: array of some type, (out) arr(p:r) is sorted.
!> p, q, r: integer, indices p is start, r is end, q = floor( (p+q)/2 ).
!> variables:
!> Left, Right: array of typeof(arr), sorted
!> l_max, r_max: integer, max index of Left or Right.
subroutine merge_int64_descending(arr, p, q, r)
integer(int64), intent(inout) :: arr(:)
integer(int32), intent(in) :: p, q, r
integer(int64) :: Left(1:q-p+1), Right(1:r-q)
integer(int32) :: l_max, r_max
l_max = q-p+1
r_max = r-q
block
!> i, j, k: integer, loop counters.
integer(int32) :: i, j, k
Left(1:l_max) = arr(p:q)
Right(1:r_max) = arr(q+1:r)
i = 1
j = 1
do k = p, r
if (Left(i) >= Right(j)) then
arr(k) = Left(i)
i = i + 1
if (i > l_max) then
arr(k+1:r) = Right(j:)
return
end if
else
arr(k) = Right(j)
j = j + 1
if (j > r_max) then
arr(k+1:r) = Left(i:)
return
end if
end if
end do
end block
end subroutine merge_int64_descending
!> merge_sort_sub: Recursive function used by merge_sort.
!> arguments:
!> arr: array of some type.
!> p, r: integer, p is start of arr, r is end of arr.
!> variables:
!> q: integer, q = floor( (p+q)/2 )
recursive subroutine merge_sort_sub_int64_descending(arr, p, r)
integer(int64), intent(inout) :: arr(:)
integer(int32), intent(in) :: p, r
integer(int32) :: q
if (p < r) then
q = (p+r)/2
call merge_sort_sub_int64_descending(arr, p, q)
call merge_sort_sub_int64_descending(arr, q+1, r)
call merge_int64_descending(arr, p, q, r)
end if
end subroutine merge_sort_sub_int64_descending
!> merge_sort_with_key_int64_descending: Sort key(:) sub function merge_sort_sub_with_key_int64_descending.
!> arguments:
!> key: array of some type.
!> indices: array of some type.
subroutine merge_sort_with_key_int64_descending(key, indices)
integer(int64), intent(inout) :: key(:)
integer(int32), intent(inout) :: indices(:)
call merge_sort_sub_with_key_int64_descending(key, indices, 1, size(key))
end subroutine merge_sort_with_key_int64_descending
!> merge_with_key: Algorithm for merge_sort, check if Left or Right is end in each loop.
!> arguments:
!> indices: array of indices.
!> key: array of some type, (out) key(p:r) is sorted.
!> p, q, r: integer, indices p is start, r is end, q = floor( (p+q)/2 ).
!> variables:
!> Left, Right: array of typeof(indices), sorted
!> l_max, r_max: integer, max index of Left or Right.
subroutine merge_with_key_int64_descending(key, indices, p, q, r)
integer(int64), intent(inout) :: key(:)
integer(int32), intent(inout) :: indices(:)
integer(int32), intent(in) :: p, q, r
integer(int32) :: Left(1:q-p+1), Right(1:r-q)
integer(int64) :: Left_key(1:q-p+1), Right_key(1:r-q)
integer(int32) :: l_max, r_max
l_max = q-p+1
r_max = r-q
block
!> i, j, k: integer, loop counters.
integer(int32) :: i, j, k
Left(1:l_max) = indices(p:q)
Right(1:r_max) = indices(q+1:r)
Left_key(1:l_max) = key(p:q)
Right_key(1:r_max) = key(q+1:r)
i = 1
j = 1
do k = p, r
if (Left_key(i) >= Right_key(j)) then
key(k) = Left_key(i)
indices(k) = Left(i)
i = i + 1
if (i > l_max) then
key(k+1:r) = Right_key(j:)
indices(k+1:r) = Right(j:)
return
end if
else
key(k) = Right_key(j)
indices(k) = Right(j)
j = j + 1
if (j > r_max) then
key(k+1:r) = Left_key(i:)
indices(k+1:r) = Left(i:)
return
end if
end if
end do
end block
end subroutine merge_with_key_int64_descending
!> merge_sort_sub_with_key: Recursive function used by merge_sort_with_key.
!> arguments:
!> indices: array of indices.
!> key: array of some type.
!> p, r: integer, p is start of arr, r is end of arr.
!> variables:
!> q: integer, q = floor( (p+q)/2 )
recursive subroutine merge_sort_sub_with_key_int64_descending(key, indices, p, r)
integer(int64), intent(inout) :: key(:)
integer(int32), intent(inout) :: indices(:)
integer(int32), intent(in) :: p, r
integer(int32) :: q
if (p < r) then
q = (p+r)/2
call merge_sort_sub_with_key_int64_descending(key, indices, p, q)
call merge_sort_sub_with_key_int64_descending(key, indices, q+1, r)
call merge_with_key_int64_descending(key, indices, p, q, r)
end if
end subroutine merge_sort_sub_with_key_int64_descending
end module merge_sort_m
program yukicoder_2852
use, intrinsic :: iso_fortran_env
use merge_sort_m
implicit none
integer(int32) :: n, k
integer(int64), allocatable :: as(:), bs(:), cs(:), diff(:)
integer(int32) :: i
read(input_unit, *) n, k
allocate(as(n), bs(n), cs(n), diff(n))
read(input_unit, *) as(:)
read(input_unit, *) bs(:)
read(input_unit, *) cs(:)
diff(:) = bs(:) - cs(:)
call merge_sort(diff)
write(output_unit, '(i0)') sum(as) + sum(cs) + sum(diff(n-k+1:n))
end program yukicoder_2852