結果
問題 | No.134 走れ!サブロー君 |
ユーザー | Authns |
提出日時 | 2020-10-18 21:40:39 |
言語 | Fortran (gFortran 13.2.0) |
結果 |
AC
|
実行時間 | 6 ms / 5,000 ms |
コード長 | 1,377 bytes |
コンパイル時間 | 433 ms |
コンパイル使用メモリ | 35,936 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-21 06:46:19 |
合計ジャッジ時間 | 1,259 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 1 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 1 ms
6,944 KB |
testcase_04 | AC | 1 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 4 ms
6,944 KB |
testcase_08 | AC | 6 ms
6,940 KB |
testcase_09 | AC | 6 ms
6,944 KB |
testcase_10 | AC | 1 ms
6,940 KB |
testcase_11 | AC | 1 ms
6,940 KB |
testcase_12 | AC | 1 ms
6,940 KB |
testcase_13 | AC | 1 ms
6,940 KB |
testcase_14 | AC | 1 ms
6,944 KB |
ソースコード
program main use,intrinsic :: iso_fortran_env implicit none integer(int32):: n,n2,s,ns,v,i,j,dx,dy integer(int32),parameter:: inf = 1001001001 integer(int32):: x0,y0 integer(int32), allocatable:: x(:),y(:) real(real64), allocatable:: dp(:,:),w(:) real(real64):: dt,ans,nw read*, x0,y0 read*, n allocate(x(n),y(n),w(n)) read*, (x(i),y(i),w(i), i=1,n) x(:)=x(:)-x0 y(:)=y(:)-y0 n2 = lshift(1,n)-1 allocate(dp(n,0:n2), source=dble(inf)) dp(1,0) = 0d0 nw = sum(w) dt = f(nw) do i=1,n ns = ibset(0,i-1) dx = abs(x(i)) dy = abs(y(i)) dp(i,0) = dble(dx+dy)*dt end do do s=0,n2 nw=0 do i=1,n if (.not.btest(s,i-1)) nw=nw+w(i) end do dt = f(nw) do v=1,n do i=1,n ns = ibset(s,i-1) if (ns==s) cycle dx = abs(x(v)-x(i)) dy = abs(y(v)-y(i)) dp(i,ns) = min(dp(i,ns), dp(v,s)+dble(dx+dy)*dt) end do end do end do ans=inf dt = f(0d0) do v=1,n dx = abs(x(v)) dy = abs(y(v)) ans=min(ans,dp(v,n2)+dble(dx+dy)*dt) end do print*, ans+dble(sum(w)) contains function f(w) real(real64):: w,f f = (w+100d0)/120d0 end function end program main