結果

問題 No.31 悪のミックスジュース
ユーザー 37zigen37zigen
提出日時 2018-04-03 07:22:03
言語 Fortran
(gFortran 14.2.0)
結果
RE  
実行時間 -
コード長 1,429 bytes
コンパイル時間 190 ms
コンパイル使用メモリ 33,116 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 07:05:28
合計ジャッジ時間 2,369 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 RE * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

module mod
    implicit none
    integer(kind=8)::n,v,c(100),ans=0
end module

program main
    use mod
    implicit none
    integer(kind=8)::i,j,k,l,r,x,y
    integer(kind=8)::vol(100)
    integer(kind=8)::dp(0:100)
    integer(kind=8)::inf=4000000000000000000_8
    read(*,*)n,v
    read*,(c(i),i=1,n)

    do i=1,n
        ans=ans+c(i)
    end do

    if(v<=n)then
        print*,ans
        return
    end if

    v=v-n

    do i=1,n
        vol(i)=1
        if(i-1>=1)then
            c(i)=c(i)+c(i-1)
            vol(i)=vol(i)+vol(i-1)
        end if
    end do


    do i=1,n
        do j=i+1,n
            if(c(i)*vol(j)>c(j)*vol(i))then
                c(i)=xor(c(i),c(j))
                c(j)=xor(c(i),c(j))
                c(i)=xor(c(i),c(j))
                vol(i)=xor(vol(i),vol(j))
                vol(j)=xor(vol(i),vol(j))
                vol(i)=xor(vol(i),vol(j))
            end if
        end do
    end do

    if(v-vol(1)>n*n)then
        x=v-n*n
        v=v-x/vol(1)*vol(1)
        ans=ans+x/vol(1)*c(1)
    end if

    do i=0,100
        dp(i)=inf
    end do
    dp(0)=0

    r=inf
    do i=1,n
        do j=v-1,0,-1
            do k=1,n
                if(j+k*vol(i)>=v)then
                    r=min(r,dp(j)+k*c(i))
                    exit
                end if
                dp(j+k*vol(i))=min(dp(j)+k*c(i),dp(j+k*vol(i)))
            end do
        end do
    end do

    print*,ans+r

end program
0