結果

問題 No.783 門松計画
コンテスト
ユーザー mai
提出日時 2017-07-01 12:51:12
言語 Ruby
(3.4.1)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,568 bytes
コンパイル時間 612 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 14,080 KB
最終ジャッジ日時 2024-07-23 12:16:04
合計ジャッジ時間 9,960 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26 TLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

line1 = gets.chomp!
abort "line 1 format error" unless line1=~/^\d+ \d+$/
line2 = gets.chomp!
abort "line 2 format error" unless line2=~/^\d+(?: \d+)*$/
line3 = gets.chomp!
abort "line 3 format error" unless line3=~/^\d+(?: \d+)*$/
abort "end of line error" unless !gets

n,cap = line1.split.map(&:to_i)
len = line2.split.map(&:to_i)
price = line3.split.map(&:to_i)

abort "N == sizeof len" unless n == len.size
abort "N == sizeof price" unless n == price.size

abort "1 <= n <= 50" unless 1 <= n && n <= 50
abort "1 <= cap <= 50" unless 1 <= cap && cap <= 50
len.each{|l|
    abort "1 <= l <= 50" unless 1 <= l && l <= 50
}
price.each{|w|
    abort "1 <= w <= 50" unless 1 <= w && w <= 50
}

# =======================================================
# format check ここまで
# =======================================================

def kadomatu?(a,b,c)
    (a!=c)&&((a<b&&b>c)||(a>b&&b<c))
end
def max(a,b);a<=b ? b : a;end


bamboo = [len,price].transpose
lenmax = len.max

dp = Array.new(cap+1){Array.new(lenmax+1){Array.new(lenmax+1,0)}}

bamboo.each{|l,w|
    dp[w][l][0] = l if w <= cap
}

result = 0

0.upto(cap-1){|cost|
    1.upto(lenmax){|pre|
        0.upto(lenmax){|prepre|
            bamboo.each{|l,w|
                if cost+w <= cap && dp[cost][pre][prepre] != 0 && (prepre==0 || kadomatu?(l,pre,prepre))
                    r = dp[cost+w][l][pre] = max(dp[cost+w][l][pre], dp[cost][pre][prepre]+l)
                    
                    result = max(result, r) if prepre != 0
                end
            }
        }
    }
}

p result
#p dp
0