結果

問題 No.783 門松計画
ユーザー maimai
提出日時 2017-07-01 12:51:12
言語 Ruby
(3.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,568 bytes
コンパイル時間 362 ms
コンパイル使用メモリ 11,392 KB
実行使用メモリ 16,844 KB
最終ジャッジ日時 2023-09-30 18:37:43
合計ジャッジ時間 8,730 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 86 ms
15,052 KB
testcase_01 AC 83 ms
15,128 KB
testcase_02 AC 81 ms
15,144 KB
testcase_03 AC 79 ms
15,236 KB
testcase_04 AC 79 ms
15,160 KB
testcase_05 AC 81 ms
15,168 KB
testcase_06 AC 80 ms
15,260 KB
testcase_07 AC 82 ms
15,284 KB
testcase_08 AC 79 ms
15,128 KB
testcase_09 AC 79 ms
15,304 KB
testcase_10 AC 718 ms
16,724 KB
testcase_11 TLE -
testcase_12 AC 1,028 ms
16,784 KB
testcase_13 AC 159 ms
15,500 KB
testcase_14 AC 429 ms
16,652 KB
testcase_15 AC 233 ms
15,732 KB
testcase_16 AC 131 ms
15,760 KB
testcase_17 AC 283 ms
16,552 KB
testcase_18 AC 87 ms
15,248 KB
testcase_19 AC 422 ms
16,484 KB
testcase_20 AC 80 ms
15,136 KB
testcase_21 AC 122 ms
15,756 KB
testcase_22 AC 131 ms
15,648 KB
testcase_23 AC 79 ms
15,120 KB
testcase_24 AC 294 ms
15,920 KB
testcase_25 AC 205 ms
16,032 KB
testcase_26 AC 321 ms
16,584 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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