結果

問題 No.324 落ちてた閉路グラフ
コンテスト
ユーザー Leonardone
提出日時 2015-12-17 10:14:58
言語 Ruby
(3.4.1)
結果
WA  
実行時間 -
コード長 2,828 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 281 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 19,876 KB
最終ジャッジ日時 2024-09-16 07:19:39
合計ジャッジ時間 7,533 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 WA * 1
other TLE * 1 -- * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
raw source code 

#! ruby
# yukicoder My Practice
# author: Leonardone @ NEETSDKASU

def gs() gets.chomp end
def gi() gets.to_i end
def gss() gets.chomp.split end
def gis() gss.map(&:to_i) end
def nmapf(n,f) n.times.map{ __send__ f } end
def arr2d(h,w,v=0) h.times.map{[v] * w} end
def ngs(n) nmapf n,:gs end
def ngi(n) nmapf n,:gi end
def ngss(n) nmapf n,:gss end
def ngis(n) nmapf n,:gis end
def for2p(hr,wr,&pr) hr.each{|i|wr.each{|j|pr.call(i,j)}} end

$N, $M = gis
$W = gis

if $M < 2
    puts 0
    exit
end

ans = $W.inject(:+)

if $N == $M
    puts ans
    exit
end

if $N - $M == 1
    puts (ans - $W.rotate(-1).zip($W).map{|x,y|x+y}.min)
    exit
end

if $M == 2
    puts [$W.max, 0].max
    exit
end

def u1(res, resi, r1, r1i, ad)
    return if r1[r1i].nil?
    if res[resi].nil? || r1[r1i] + ad > res[resi]
        res[resi] = r1[r1i] + ad
    end
end

def u2(res, r1, a1)
    r1.size.times do |i|
        (0..3).each do |j|
            next if r1[i][j].nil?
            k = a1[j]
            if res[i][k].nil? || r1[i][j] > res[i][k]
                res[i][k] = r1[i][j]
            end
        end
    end
end  

def u3(res, r1, a1, a2, xm, t)
    [r1.size, $M - 2].min.times do |i|
        
        if t == 0
            4.times {|j| u1 res[i + 1], a2[j], r1[i], j, $W[xm] }
        else
            [[a1, $W[xm]], [a2, 0]].each do |a,d|
                4.times {|j| u1 res[i + 1], a[j], r1[i], j, d }
            end
            if t > 1
                4.times {|j| u1 res[i + 1], a1[j], r1[i], j, 0 }
            end
        end
    end
end

def u4(res, resi, r1, r1i, r2, r2i, ad)
    return if r1[r1i].nil? || r2[r2i].nil?
    if res[resi].nil? || r1[r1i] + r2[r2i] + ad > res[resi]
        res[resi] = r1[r1i] + r2[r2i] + ad
    end
end

def f(x1,x2)
    return [] if x1 == x2
    n = x2 - x1
    return [[nil, nil, $W[x1], nil]] if n == 1
    
    xm = (x1 + x2) >> 1
    r1 = f(x1, xm)
    r2 = f(xm + 1, x2)
    res = [n + 1, $M - 1].min.times.map{ [nil, nil, nil, nil] }
    
    res[0][0] = $W[xm]
    
    u2 res, r1, [0, 1, 1, 0]
    u2 res, r2, [0, 0, 3, 3]
    u3 res, r1, [0, 1, 1, 0], [3, 2, 2, 3], xm, x2 - (xm + 1)
    u3 res, r2, [0, 0, 3, 3], [1, 1, 2, 2], xm, xm - x1
    
    r1.size.times do |i|
        r2.size.times do |j|
            k = (i + 2) + (j + 2) - 2
            break if k >= $M - 1
            4.times do |t1|
                e1, e2 =[ [[0,0,3,3], [0,0,0,0]], [[1,1,2,2],[0,0,0,0]], 
                    [[1,1,2,2],[0,$W[xm],$W[xm],0]], [[0, 0, 3, 3], [0, $W[xm], $W[xm], 0]] ][t1]
                4.times do |t2|
                    u4 res[k], e1[t2], r1[i], t1, r2[j], t2, e2[t2]
                end
            end
        end
    end
    
    return res
end

r = f(0, $N - 1)[$M - 2]
r[2] += $W[$N - 1]

a = 0
if $M * 2 > $N
    a = $W.take($M * 2 - $N).inject(:+)
end

p (r + [a]).max
0