Problem p02888 (python)

Fixed submission:
N = int(input())
L = list(map(int,input().split()))
L.sort()
ans = 0
import bisect
for i in range(N-2):
    a = L[i]
    for j in range(i+1,N-1):
        b = L[j]
        k = bisect.bisect_left(L,a+b)
        l = bisect.bisect_left(L,b-a)
        ans += k-max(j+1,l)
print(ans)

Buggy submission (verdict: Runtime Error):

N = int(input())
L = list(map(int,input().split()))
L.sort()
ans = 0
import bisect
for i in range(N-2):
    
    for j in range(i+1,N-1):
        a = L[i]
        b = L[j]
        k = bisect.bisect_left(L,a+b)
        l = bisect.bisect_left(L,b-a)
        ans += k-max(j+1,l)
print(ans)

"""
N,M,L = map(int,input().split())
## ダイクストラ法とは、グラフの""""""を求めるアルゴリズム
## 条件として、1.グラフに負辺がないこと(もちろん負の閉路はない)が必要
## DP的な発想
## 計算量はO((V+E)logV)
import heapq # 二分ヒープ
class Dijkstra: # 最短経路問題 V=ノード数,E=エッジ数とすると、計算量はO((V+E)logV)
    def __init__(self, route_map, start_point, goal_point=None):
        self.route_map = route_map #
        self.start_point = start_point # スタート位置
        self.goal_point = goal_point

    def execute(self):
        
        num_of_city = len(self.route_map) # ノード数
        dist = [float("inf") for _ in range(num_of_city)] # startからの距離を格納する
        prev = [float("inf") for _ in range(num_of_city)] # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる
        dist[self.start_point] = 0 # スタート位置までのコストは0
        heap_q = [] # 優先度つきキュー
        heapq.heappush(heap_q, (0, self.start_point)) # タプル(0,スタート位置)をheap_qに追加
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q) # 直前にheap_qに入れたタプルから取り出す(src＝ソース)
            if dist[src] < prev_cost: # もし、スタート位置からsrcまでの距離がprev_costより小さいなら問題ないのでok
                continue
            for dest, cost in self.route_map[src].items(): # destはsrcから行ける頂点(目的地)
                if cost != float("inf") and dist[dest] > dist[src] + cost: # もし、destに有限のコストで行けて、srcからdestに行くのがスタートからの現状の最短距離になるなら、(単純な枝刈り by yosupot)
                    dist[dest] = dist[src] + cost # 更新する
                    heapq.heappush(heap_q, (dist[dest], dest)) # 更新したのでheap_qに入れておく。次のノードに移動した時に取り出して無駄な変更がないか確認する
                    prev[dest] = src
        if self.goal_point is not None: # ゴールまでの最短経路を返す
            return self.get_path(self.goal_point, prev)
        else: # スタートから各頂点までの最短距離を格納したリストを返す
            return dist

    def get_path(self, goal, prev):  # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる
        
        dest = goal # 目的地
        path = [goal] # 目的地の直前のノード
        while prev[dest] != float("inf"): # prev[start]はfloat("inf")になり、停止する
            
            path.append(prev[dest]) # 後ろから戻っていく
            dest = prev[dest]
        return list(reversed(path)) # 逆から辿ったので順を元に戻す

# 上のDijkstraを使う場合、隣接行列は辞書型でなくてはならない

D = [dict() for _ in range(N)]

for i in range(M):
    a,b,c = map(int,input().split())
    D[a-1][b-1] = c
    D[b-1][a-1] = c

Q = int(input())
for q in range(Q):  
    s,t = map(int,input().split())
    s-=1
    t-=1
    Dist = Dijkstra(D,s,t)
    path = Dist.execute()
    print(path)
    if len(path)==1:
        print(-1)
    else:
        now = L
        ans = 0
        for i in range(1,len(path)):
            if now>=D[path[i]][path[i-1]]:
                now -= D[path[i]][path[i-1]]
            else:
                ans += 1
                now = L+now-D[path[i]][path[i-1]]
        print(ans)

"""
N = int(input())
A = list(map(int,input().split()))
A.sort()
def RLE(S): # 文字列のランレングス圧縮(RunLengthEncoding)
    res = []
    if len(S)==0:
        return res
    now = S[0]
    id = 1
    num = 1
    while id < len(S):
        if now==S[id]:
            num+=1
            id+=1
        else:
            res.append(num)
            now=S[id]
            num=1
            id+=1
    res.append(num)
    return res # list[tuple(str,int),...]
B = RLE(A)
B.sort()

class BIT():
    def __init__(self,n):
        self.unity_sum = 0
        self.n = n
        self.dat = [0]*(n+1)


    def add(self,a,x): # a(0-indexed)番目の要素がx個追加される
        a += 1 # 本来は1-indexedなのでここで調整
        i = a
        while i < self.n:
            self.dat[i] += x
            i += i&-i

    def sum1(self,a): # 1番目からa(0-indexed)番目の要素の個数の総和
        a += 1 # 本来は1-indexedなのでここで調整
        i = a
        res = 0
        while i > 0:
            res += self.dat[i]
            i -= i&-i
        return res

    def sum2(self,a,b): # [a,b) a(0-indexed)番目からb(0-indexed)番目の要素の個数の総和
        return(sum1(b)-sum1(a))

    def search(self,k): # k(0-indexed)番目の数を二分探索
        k += 1
        res = 0
        N = 1
        while N < self.n:
            N *= 2

        i = N // 2
        while i > 0:
            if res+i < self.n and dat[res+i] < k:
                k -= dat[res+i]
                res += i
                i //= 2
        return res+1

T = BIT()