Submission #61804733

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import math
import pypyjit
pypyjit.set_param("max_unroll_recursion=-1")
def solve():
    N,M=map(int,input().split())
    P=list(map(int,input().split()))
    s=0.0
    for x in P:
        s+=1.0/x
    def can(t):
        rc=(t*t)/s
        if rc> M:
            return False
        k=[0]*N
        f=[0.0]*N
        sf=0
        for i in range(N):
            v=(t/(P[i]*s))
            fv=int(v)
            k[i]=fv
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import math
import pypyjit
pypyjit.set_param("max_unroll_recursion=-1")

def solve():
    N,M=map(int,input().split())
    P=list(map(int,input().split()))
    s=0.0
    for x in P:
        s+=1.0/x
    def can(t):
        rc=(t*t)/s
        if rc> M:
            return False
        k=[0]*N
        f=[0.0]*N
        sf=0
        for i in range(N):
            v=(t/(P[i]*s))
            fv=int(v)
            k[i]=fv
            sf+=fv
            f[i]=v-fv
        r=t-sf
        if r<0: return False
        if r>0:
            idx=sorted(range(N),key=lambda i:f[i],reverse=True)
            for i in range(r):
                k[idx[i]]+=1
        c=0
        for i in range(N):
            c+=P[i]*(k[i]*k[i])
            if c> M: return False
        return c<=M
    l=0
    h=int(math.isqrt(N*M))+2
    ans=0
    while l<=h:
        m=(l+h)//2
        if can(m):
            ans=m
            l=m+1
        else:
            h=m-1
    print(ans)

solve()

Submission Info

Judge Result