Skip to content

Instantly share code, notes, and snippets.

@akiradeveloper
Last active July 23, 2019 07:07
Show Gist options
  • Save akiradeveloper/f4a0a11cca64cef506d2467c7390d567 to your computer and use it in GitHub Desktop.
Save akiradeveloper/f4a0a11cca64cef506d2467c7390d567 to your computer and use it in GitHub Desktop.
AOJ0529 TLE
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0529
TEST=[]
(n,m) = map(int, input().split())
while (n,m) != (0,0):
ps = [0]
for _ in range(n):
p = int(input())
ps.append(p)
TEST.append((m, ps))
(n,m) = map(int, input().split())
import bisect
def solve(m, ps):
n = len(ps)
comb = []
for i in range(n):
for j in range(n):
comb.append(ps[i]+ps[j])
comb.sort()
max_v = 0
for a in comb:
rest = m - a
i = bisect.bisect_left(comb, rest)
if i-1 >= 0:
v = comb[i-1]+a
if v <= m:
max_v = max(v, max_v)
if i < len(comb):
v = comb[i]+a
if v <= m:
max_v = max(v, max_v)
if i+1 < len(comb):
v = comb[i+1]+a
if v <= m:
max_v = max(v, max_v)
return max_v
for (m, ps) in TEST:
print(solve(m, ps))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment