Google Kickstart 2019 Round E-Problem B

, ,
1

I did exactly what that is mentioned in the editorial but it still throws TLE for second Test Set. Can anyone please help me find any optimizations for this code?
Link: Kick Start - Google’s Coding Competitions

prefix_eating=[0]*(100001)
suffix_coding=[0]*(100001)
from bisect import *
            
def solve_optimized():
    values.sort(key=lambda x:x[2])
    slots=s
    prefix_eating[0]=values[0][1]
    suffix_coding[slots-1]=values[-1][0]
    # Making prefix and sufix sum arrays
    for i in range(1,slots):
        prefix_eating[i]=values[i][1]+prefix_eating[i-1]
        end=slots-1-i
        suffix_coding[end]=values[end][0]+suffix_coding[end+1]
    # print(prefix_eating)
    # print(suffix_coding)
    for _ in range(d):
        tc,te=input().split()
        tc=int(tc)
        te=int(te)
        ind=bisect_left(prefix_eating,te,0,slots)
        # Find residue coding that can be obtained from above slot
        verdict=True
        ind=min(ind,slots-1)
        extra_eating=prefix_eating[ind]-te
        if extra_eating>0:
            f=(values[ind][1]-extra_eating)/values[ind][1]
            tc=tc-(1-f)*values[ind][0]
            tc=max(tc,0)
        if ind+1>=slots:
            if tc!=0 or prefix_eating[slots-1]<te:
                verdict=False
        else:
            if suffix_coding[ind+1]<tc:
                verdict=False

        if verdict:
            print("Y",end="")
        else:
            print("N",end="")

for t in range(int(input())):
    d,s=input().split()
    d=int(d)
    s=int(s)
    values=[]
    for _ in range(s):
        ci,ei=input().split()
        ci=int(ci)
        ei=int(ei)
        values.append((ci,ei,ci/ei))
    print("Case #{}: ".format(t+1),end="")
    solve_optimized()
    print()
1 Like