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()