Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], skipTags: ["script","noscript","style","textarea","code"], processEscapes: true }});

問題文

実数変数 $x_1, x_2, ..., x_N$ は以下の条件を満たす。

$0 \leq x_i \leq 1$ ($1 \leq i \leq N$)

$w_1x_1+w_2x_2+...+w_Nx_N \leq W$

このとき $v_1x_1+v_2x_2+...+v_Nx_N$ のとりうる最大値を求めよ。そのような最大値は実際に存在することが知られている。

入力

入力は以下の形式に従う。与えられる数は全て整数である。

$N$ $W$
$w_1$ $v_1$
$w_2$ $v_2$
$...$
$w_N$ $v_N$

制約

$1 \leq N \leq 10^5$

$1 \leq W \leq 10^5$

$-10^4 \leq w_i \leq 10^4$

$-10^4 \leq v_i \leq 10^4$

出力

$v_1x_1+v_2x_2+...+v_Nx_N$ のとりうる最大値を1行に出力せよ。
出力には $10^{-3}$ を超える誤差があってはならない。

Sample Input 1

1 1
3 1

Output for the Sample Input 1

0.333333

$x_1=1/3$ のとき最大となる。

Sample Input 2

2 3
3 3
1 2

Output for the Sample Input 2

4.000000

Sample Input 3

2 1
-1 -3
3 10

Output for the Sample Input 3

3.666667



Sample input:
1 1
3 1


Sample output:
0.333333

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

ri=(raw_input()).split(" ")
n=int(ri[0])
w=int(ri[1])
d=[0]*n
dp=[]
dm=[]
restrict=0.0
result=0.0

for i in range(n):
    ri=(raw_input()).split(" ")
    d[i]=[0]*3
    d[i][1]=int(ri[0])*1.0 #w
    d[i][2]=int(ri[1])*1.0 #v
    if d[i][1]<=0 and d[i][2]>=0:
        restrict+=d[i][1]
        result+=d[i][2]
    elif (d[i][1]>0 and d[i][2]>0):
        dp+=[[1.0*d[i][1]/d[i][2],d[i][1],d[i][2],0.0]]
    elif (d[i][1]<0 and d[i][2]<0):
        dm+=[[-1.0*d[i][1]/d[i][2],d[i][1],d[i][2],0.0]]

dp=sorted(dp)
dm=sorted(dm)
dmidx=0

for i in range(len(dp)):
    if dp[i][1]+restrict<=w:
        restrict+=dp[i][1]
        result+=dp[i][2]
        dp[i][3]=1.0
    else:
        dp[i][3]=1.0*(w-restrict)/dp[i][1]
        restrict=w
        result+=dp[i][2]*dp[i][3]
        cont=True if (len(dm)>0 and (dp[i][0]<(-dm[dmidx][0]))) else False
        while cont:
            if (1-dp[i][3])*dp[i][1]/(-dm[dmidx][1])<1-dm[dmidx][3]:
                dm[dmidx][3]+=(1-dp[i][3])*dp[i][1]/(-dm[dmidx][1])
                result+=(1-dp[i][3])*(dp[i][2]-dm[dmidx][2]*dp[i][1]/dm[dmidx][1])
                dp[i][3]=1.0
                cont=False
            else:
                dp[i][3]+=(1-dm[dmidx][3])*(-dm[dmidx][1])/dp[i][1]
                result+=(1-dm[dmidx][3])*(dm[dmidx][2]+dp[i][2]*(-dm[dmidx][1])/dp[i][1])
                dm[dmidx][3]=1.0
                dmidx+=1
                if dmidx>=len(dm):
                    cont=False
                elif dp[i][0]>=(-dm[dmidx][0]):
                    cont=False
                
#print(dp)
#print(dm)
#print(restrict)
print(result)

Submission status: Accepted

Solution code:
import heapq
N, W = [int(n) for n in input().split()]
tmpw = 0
tmpv = 0
minheap = []
for i in range(N):
    w, v = [int(n) for n in input().split()]
    if(w < 0):
        tmpw += w
        tmpv += v
        w *= -1
        v *= -1
    if(v > 0):
        if w == 0:
            tmpv += v
        else:
            heapq.heappush(minheap, (-(v/w), w, v))
while(W-tmpw > 1e-9 and not minheap == []):
    p = heapq.heappop(minheap)
    w = p[1]
    v = p[2]
    x = min(1, (W-tmpw)/w)
    tmpw += x*w
    tmpv += x*v
print(tmpv)