Problem:


Score : 300 points

Problem Statement

There are N boxes arranged in a row.
Initially, the i-th box from the left contains a_i candies.

Snuke can perform the following operation any number of times:

Choose a box containing at least one candy, and eat one of the candies in the chosen box.

His objective is as follows:

Any two neighboring boxes contain at most x candies in total.

Find the minimum number of operations required to achieve the objective.

Constraints

2 ≤ N ≤ 10^5

0 ≤ a_i ≤ 10^9

0 ≤ x ≤ 10^9

Input

The input is given from Standard Input in the following format:

N x
a_1 a_2 ... a_N

Output

Print the minimum number of operations required to achieve the objective.

Sample Input 1

3 3
2 2 2

Sample Output 1

1

Eat one candy in the second box.
Then, the number of candies in each box becomes (2, 1, 2).

Sample Input 2

6 1
1 6 1 2 0 4

Sample Output 2

11

For example, eat six candies in the second box, two in the fourth box, and three in the sixth box.
Then, the number of candies in each box becomes (1, 0, 1, 0, 0, 1).

Sample Input 3

5 9
3 1 4 1 5

Sample Output 3

0

The objective is already achieved without performing operations.

Sample Input 4

2 0
5 5

Sample Output 4

10

All the candies need to be eaten.



Sample input:
3 3
2 2 2


Sample output:
1

Submission status: Runtime Error

Solution code:
import numpy as np

xs, ys, xt, yt = [int(x) for x in input().split(' ')]
n = int(input())
cirl = []
for i in range(n):
    cirl.append([int(x) for x in input().split(' ')])
cirl = [[xs, ys, 0]] + cirl + [[xt, yt, 0]]
use = [x for x in range(n+2)]
weigth = [0] + [10**10 for x in range(n+1)]
while min(weigth) != weigth[n+1]:
    chos = weigth.index(min(weigth))
    use.remove(chos)
    x1, y1, r1 = cirl[chos][0], cirl[chos][1], cirl[chos][2]
    for i in use:
        x2, y2, r2 = cirl[i][0], cirl[i][1], cirl[i][2]
        dist = np.sqrt((y2-y1)**2 + (x2-x1)**2) - (r1+r2)
        print(dist)
        if dist < 0:
            dist = 0
        if dist + weigth[chos] < weigth[i]:
            weigth[i] = dist + weigth[chos]
    weigth[chos] = 10**10
print(weigth[n+1])

Submission status: Runtime Error

Solution code:
from math import sqrt

class Edge:
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost

def dijkstra(G, s):
    from heapq import heappush, heappop
    l = len(G)
    dist = [float('inf')] * l
    done = [False] * l
    dist[s] = 0
    pq = []
    heappush(pq, (0, s))
    while pq:
        c, v = heappop(pq)
        done[v] = True
        for e in G[v]:
            cost = dist[v] + e.cost
            if cost < dist[e.to] and not done[e.to]:
                dist[e.to] = cost
                heappush(pq, (cost, e.to))
    return dist

xs, ys, xt, yt = map(int, input().split())
N = int(input())
xyr = [[int(i) for i in input().split()] for _ in range(N)]
xyr += [[xs, ys, 0], [xt, yt, 0]]

G = [[] for _ in range(N + 2)]

for i, (x, y, r) in enumerate(xyr):
    for j, (x2, y2, r2) in enumerate(xyr[i + 1:]):
        w = max(0, sqrt((x - x2)**2 + (y - y2)**2) - r - r2)
        G[i].append(Edge(i + j + 1, w))
        G[i + j + 1].append(Edge(i, w))

print(dijkstra(G, len(G) - 2)[-1])

Submission status: Runtime Error

Solution code:
from math import hypot
def dijkstra(matrix):
    from heapq import heappush, heappop
    n = len(matrix)
    inf = 10**10
    hq = []
    ans = [inf]*n
    ans[0] = 0
    heappush(hq, (0, 0))
    while hq:
        d, p = heappop(hq)
        for i in range(n):
            if ans[p] == d and p != i and d + matrix[p][i] < ans[i]:
                ans[i] = d + matrix[p][i]
                heappush(hq, (ans[i], i))
    return ans[n-1]

x_s, y_s, x_t, y_t = map(int, input().split())
N = int(input())
xyr = [(x_s,y_s,0)]
for i in range(N):
    xyr.append(tuple(int(i) for i in input().split()))
xyr.append((x_t,y_t,0))
graph = [[0]*(N+2) for j in range(N+2)]

for i in range(N+2):
    for j in range(i,N+2):
        graph[i][j] = max(hypot((xyr[i][1]-xyr[j][1]), (xyr[i][0]-xyr[j][0])) - xyr[i][2] - xyr[j][2], 0)
        graph[j][i] = graph[i][j]

print(dijkstra(graph))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env pypy3

import math
import itertools


INVALID = -1
INF = 10 ** 12


def dijkstra_dense(num_vs, adj_matrix, source, dest):
    dist = [INF for _ in range(num_vs)]
    visited = [False for _ in range(num_vs)]
    dist[source] = 0
    while True:
        try:
            u = min((j for j in range(num_vs) if not visited[j]),
                    key=lambda i: dist[i])
        except ValueError:
            break
        if dist[u] == INF:
            break
        visited[u] = True
        for v in range(num_vs):
            w = adj_matrix[u][v]
            if u != v and w < INF:
                new_len = dist[u] + w
                if new_len < dist[v]:
                    dist[v] = new_len
    return dist[dest]


def main():
    # 始点を頂点0、終点を頂点N + 1とする
    x0, y0, xf, yf = (int(x) for x in input().split())
    n = int(input())
    xs = [None for _ in range(n + 2)]
    ys = [None for _ in range(n + 2)]
    rs = [None for _ in range(n + 2)]
    xs[0], ys[0], rs[0] = x0, y0, 0
    xs[n + 1], ys[n + 1], rs[n + 1] = xf, yf, 0
    for i in range(1, n + 1):
        xs[i], ys[i], rs[i] = (int(z) for z in input().split())
    adj_matrix = [[INF for _ in range(n + 2)] for _ in range(n + 2)]
    for i, j in itertools.product(range(n + 2), repeat=2):
        adj_matrix[i][j] = max(0, math.hypot(xs[i] - xs[j],
                                             ys[i] - ys[j]) - (rs[i] + rs[j]))
    res = dijkstra_dense(n + 2, adj_matrix, 0, n + 1)
    print("{:.12f}".format(res))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import math
import itertools


INVALID = -1
INF = 10 ** 12


def dijkstra_dense(num_vs, adj_matrix, source, dest):
    dist = [INF for _ in range(num_vs)]
    visited = [False for _ in range(num_vs)]
    dist[source] = 0
    while True:
        u = min((j for j in range(num_vs) if not visited[j]),
                key=lambda i: dist[i], default=INVALID)
        if u == INVALID or dist[u] == INF:
            break
        visited[u] = True
        for v in range(num_vs):
            w = adj_matrix[u][v]
            if u != v and w < INF:
                new_len = dist[u] + w
                if new_len < dist[v]:
                    dist[v] = new_len
    return dist[dest]


def main():
    # 始点を頂点0、終点を頂点N + 1とする
    x0, y0, xf, yf = (int(x) for x in input().split())
    n = int(input())
    xs = [None for _ in range(n + 2)]
    ys = [None for _ in range(n + 2)]
    rs = [None for _ in range(n + 2)]
    xs[0], ys[0], rs[0] = x0, y0, 0
    xs[n + 1], ys[n + 1], rs[n + 1] = xf, yf, 0
    for i in range(1, n + 1):
        xs[i], ys[i], rs[i] = (int(z) for z in input().split())
    adj_matrix = [[INF for _ in range(n + 2)] for _ in range(n + 2)]
    for i, j in itertools.product(range(n + 2), repeat=2):
        adj_matrix[i][j] = max(0, math.hypot(xs[i] - xs[j],
                                             ys[i] - ys[j]) - (rs[i] + rs[j]))
    res = dijkstra_dense(n + 2, adj_matrix, 0, n + 1)
    print("{:.12f}".format(res))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
import heapq
def dijkstra(s,m,n):
    visited=[0]*n
    d=[float("inf")]*n
    d[s]=0
    while True:
        mincost=float("inf")
        for i in xrange(n):
            if visited[i]!=2 and d[i]<mincost:
                mincost=d[i]
                u=i
        if mincost==float("inf"):
            break
        visited[u]=2
        for v in xrange(n):
            if visited[v]!=2:
                if d[u]+m[u][v]<d[v]:
                    d[v]=d[u]+m[u][v]
                    visited[v]=1
    return d

def main():
    xs,ys,xt,yt=map(int,raw_input().split())
    n=int(raw_input())
    c=[[xs,ys,0]]+[map(int,raw_input().split()) for _ in xrange(n)]+[[xt,yt,0]]
    dist=[[float("inf")]*(n+2) for _ in xrange(n+2)]
    for i in xrange(n+2):
        for j in xrange(n+2):
            if i==j:continue
            dist[i][j]=min(dist[i][j],dist[j][i],max(math.sqrt(abs(c[i][0]-c[j][0])**2+abs(c[i][1]-c[j][1])**2)-c[i][2]-c[j][2],0))
            dist[j][i]=dist[i][j]
    ans=dijkstra(0,dist,n+2)
    print(ans[n+1])
main()

Submission status: Runtime Error

Solution code:
def get_input(f, n):
    l = [f(x) for x in input().split()]
    if n==1:
        return l[0]
    else:
        return l

N, x = get_input(int, 2)
As = get_input(int, N)

Bs = [As[i]+As[i+1] for i in range(N-1)]

result = 0
for idx in range(N-2):
    if Bs[idx] > x:
        if Bs[idx+1] > x:
            la = max(Bs[idx], Bs[idx+1])
            ex = la - x
            if ex > As[idx+1]:
                su = ex - As[idx+1]
                Bs[idx+1] -= su
                As[idx+2] -= su
                result += su
                if (Bs[idx] - x - su > 0):
                    results += (Bs[idx]-x-su)
            else:
                Bs[idx+1] -= ex
                result += ex
        else:
            result += Bs[idx] - x

idx = N-2
if Bs[idx] > x:
    result += Bs[idx] - x


print(result)

Submission status: Runtime Error

Solution code:
from math import sqrt
inf = 10**10
x_s, y_s, x_t, y_t = map(int, input().split())
N = int(input())
xyr = []
for i in range(N):
	x_i, y_i, r_i = map(int, input().split())
	xyr.append((x_i, y_i, r_i))
p = (x_s, y_s)
goal = (x_t, y_t)
ans = 0
while p != goal and xyr:
	D = inf
	for i in range(N):
		x, y, r = xyr[i]
		d = sqrt((x-p[0])**2+(y-p[1])**2) - 2*r
		if d < D:
			j = i
			D = d
	d = sqrt((goal[0]-p[0])**2+(goal[1]-p[1])**2)
	if d < D:
		ans += d
		p = goal
	else:
		x, y, r = xyr.pop(j)
		p = (x, y)
		N -= 1
		ans += D

if p != goal:
	d = sqrt((goal[0]-p[0])**2+(goal[1]-p[1])**2)
	ans += d

print(max(0, ans))

Submission status: Runtime Error

Solution code:
import math
def dis(x1,y1,r1,x2,y2,r2):
    if math.sqrt(abs(x1-x2)**2+abs(y1-y2)**2)>r1+r2:
        return  math.sqrt(abs(x1-x2)**2+abs(y1-y2)**2)-r1-r2
    else:
        return 0
import heapq

def dijkstra(s,g,c,n):
    d=[float('inf')]*n
    d[s]=0
    pq=[]
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        if d[u]<t:
            continue
        for v in g[u]:
            if d[u]+c[u][v]<d[v]:
                d[v]=d[u]+c[u][v]
                heapq.heappush(pq,[d[v],v])
    return d
def main():
    xs,ys,xt,yt=map(int,raw_input().split())
    n=int(raw_input())
    c=[[xs,ys,0]]+[map(int,raw_input().split()) for _ in xrange(n)]+[[xt,yt,0]]
    g=[[] for _ in xrange(n+2)]
    dist=[[float("inf")]*(n+2) for _ in xrange(n+2)]
    for i in xrange(n+2):
        for j in xrange(n+2):
            if i==j:continue
            g[i].append(j)
            dist[i][j]=min(dist[i][j],dis(c[i][0],c[i][1],c[i][2],c[j][0],c[j][1],c[j][2]))
    ans=dijkstra(0,g,dist,n+2)
    print(ans[n+1])
main()

Submission status: Runtime Error

Solution code:
xs,ys,xt,yt = map(int, input().split())
n = int(input())
c = [(xs,ys, 0),(xt,yt,0)]
for i in range(n):
    x,y,r = map(int, input().split())
    c.append((x,y,r))

def circle_circle(ax,ay,ar,bx,by,br):
    d =((ax-bx)**2 + (ay-by)**2)**0.5
    return max(0, d-(ar+br))

def dijkstra(V, edges, root):
    import heapq

    visited = [False] * V
    nodes = [[] for i in range(V)]
    cost = [[] for i in range(V)]

    for e in edges:
        s, t, d = e
        nodes[s].append(t)
        cost[s].append(d)

    dist = [float('inf')] * V
    dist[root] = 0

    h = [(0, root)]
    while h:
        c, v = heapq.heappop(h)
        if visited[v]:
            continue
        visited[v] = True
        for i in range(n+1):
            t = nodes[v][i]
            nc = c + cost[v][i]
            if dist[t] > nc:
                dist[t] = nc
                heapq.heappush(h, (nc, t))
    return dist
edges = []
for i in range(n+1):
    for j in range(i+1, n+2):
        d = circle_circle(c[i][0],c[i][1],c[i][2],c[j][0],c[j][1],c[j][2])
        edges.append((i,j,d))
        edges.append((j,i,d))
dij = dijkstra(n+2, edges, 0)
print(dij[1])

Submission status: Runtime Error

Solution code:
xs,ys,xt,yt = map(int, input().split())
n = int(input())
c = [(xs,ys, 0),(xt,yt,0)]
for i in range(n):
    x,y,r = map(int, input().split())
    c.append((x,y,r))

def circle_circle(ax,ay,ar,bx,by,br):
    d =((ax-bx)**2 + (ay-by)**2)**0.5
    return max(0, d-(ar+br))

def dijkstra(V, edges, root):
    import heapq

    visited = [False] * V
    nodes = [[] for i in range(V)]
    cost = [[] for i in range(V)]

    for e in edges:
        s, t, d = e
        nodes[s].append(t)
        cost[s].append(d)

    dist = [float('inf')] * V
    dist[root] = 0

    h = [(0, root)]
    while h:
        c, v = heapq.heappop(h)
        if visited[v]:
            continue
        visited[v] = True
        for i in range(len(nodes[v])):
            t = nodes[v][i]
            nc = c + cost[v][i]
            if dist[t] > nc:
                dist[t] = nc
                heapq.heappush(h, (nc, t))
    return dist
edges = []
for i in range(n+1):
    for j in range(i+1, n+2):
        d = circle_circle(c[i][0],c[i][1],c[i][2],c[j][0],c[j][1],c[j][2])
        edges.append((i,j,d))
        edges.append((j,i,d))
dij = dijkstra(n+2, edges, 0)
print(dij[1])