結果

問題 No.783 門松計画
ユーザー maimai
提出日時 2017-07-01 12:51:12
言語 Ruby
(3.3.0)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 84 ms
11,904 KB
testcase_01 AC 84 ms
11,776 KB
testcase_02 AC 84 ms
11,904 KB
testcase_03 AC 84 ms
11,776 KB
testcase_04 AC 89 ms
12,160 KB
testcase_05 AC 83 ms
11,904 KB
testcase_06 AC 85 ms
11,776 KB
testcase_07 AC 84 ms
12,032 KB
testcase_08 AC 84 ms
12,032 KB
testcase_09 AC 89 ms
12,160 KB
testcase_10 AC 848 ms
13,696 KB
testcase_11 TLE -
testcase_12 AC 1,202 ms
13,824 KB
testcase_13 AC 179 ms
12,416 KB
testcase_14 AC 476 ms
13,440 KB
testcase_15 AC 261 ms
12,288 KB
testcase_16 AC 145 ms
12,416 KB
testcase_17 AC 323 ms
13,568 KB
testcase_18 AC 95 ms
12,416 KB
testcase_19 AC 463 ms
13,184 KB
testcase_20 AC 86 ms
11,904 KB
testcase_21 AC 133 ms
12,288 KB
testcase_22 AC 142 ms
12,288 KB
testcase_23 AC 85 ms
11,904 KB
testcase_24 AC 330 ms
12,800 KB
testcase_25 AC 231 ms
12,544 KB
testcase_26 AC 364 ms
13,312 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