Getting TLE for EKO (even after using binary search)

[sksharma]

I guess I am using the most optimal solution, don’t know what else can be optimized. Can anyone help? Thanks.

import sys
from sys import stdin, stdout
from math import sqrt,gcd
from collections import deque
sys.setrecursionlimit(10**8)
ip = lambda :stdin.readline()
I     = lambda :int(ip())
S     = lambda :ip().strip()
M     = lambda :map(int,ip().strip().split())
L     = lambda :list(map(int,ip().strip().split()))
mod=1000000007

##########################################################

def valid(m):
	if marr>=m:
		if sarr-n*m>=M:
			return True
		else:
			return False
	s=0
	for i in arr:
		if i>m:
			s+=i-m
		if s>=M:
			return True
	return False
n,M=M()
arr=L()
sarr=sum(arr)
marr=min(arr)
l,r=0,max(arr)
ans=r
while l<=r:
	m=(l+r)//2
	if valid(m):
		ans=m
		l=m+1
	else:
		r=m-1
stdout.write(str(ans))

[simes]

sarr=sum(arr)
marr=min(arr)
l,r=0,max(arr)

OK, I don’t know Python much at all, so I might be talking rubbish, but wouldn’t each of those calls need to iterate through the whole array to return the sum, min or max? Isn’t that going to take some time when the array has 1 million elements? Would it be quicker to write an explicit loop to iterate through the array just once?

[sksharma]

Yes, your point is valid, it will take extra time, but if we talk about time complexity then it shouldn’t matter much because all these are O(n) operations. Anyways, I tried your suggestion but still tle. Maybe the compiler is not optimized for python solutions.