Problem:


Score : 700 points

Problem Statement

We have N gemstones labeled 1 through N.

You can perform the following operation any number of times (possibly zero).

Select a positive integer x, and smash all the gems labeled with multiples of x.

Then, for each i, if the gem labeled i remains without getting smashed, you will receive a_i yen (the currency of Japan).
However, a_i may be negative, in which case you will be charged money.

By optimally performing the operation, how much yen can you earn?

Constraints

All input values are integers.

1 \leq N \leq 100

|a_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the maximum amount of money that can be earned.

Sample Input 1

6
1 2 -6 4 5 3

Sample Output 1

12

It is optimal to smash Gem 3 and 6.

Sample Input 2

6
100 -100 -100 -100 100 -100

Sample Output 2

200

Sample Input 3

5
-1 -2 -3 -4 -5

Sample Output 3

0

It is optimal to smash all the gems.

Sample Input 4

2
-1000 100000

Sample Output 4

99000



Sample input:
6
1 2 -6 4 5 3


Sample output:
12

Submission status: Accepted

Solution code:
from collections import deque

# グラフに辺を追加する
def addEdge(adjL, vFr, vTo, cap):
    adjL[vFr].append([vTo, cap, len(adjL[vTo])])
    adjL[vTo].append([vFr, 0, len(adjL[vFr]) - 1]) # 逆辺


# Edmonds-Karp法（最大フローを求める）
def Edmonds_Karp(adjL, vSt, vEn):

    # 残余グラフの始点から終点までの経路（増加パス）を、BFSで探索する
    def BFS(vSt, vEn):
        prev = [-1] * numV
        prev[vSt] = None
        iE = [-1] * numV
        df = 0
        Q = deque([(vSt, float('inf'))])
        while Q:
            vNow, fNow = Q.popleft()
            if vNow == vEn:
                # 終点に到達したら、ループを抜ける
                df = fNow
                break

            for i, (v2, cap, iRev) in enumerate(adjL[vNow]):
                if prev[v2] == -1 and cap > 0:
                    # 未探索の頂点への辺の容量に空きがある場合、探索する
                    prev[v2] = vNow
                    iE[v2] = (i, iRev)
                    Q.append((v2, min(fNow, cap)))

        if df > 0:
            # 始点から終点までの経路を遡って、辺のフローを変更する
            vNow = vEn
            while vNow != vSt:
                v0 = prev[vNow]
                e, iRev = iE[vNow]
                adjL[v0][e][1] -= df
                adjL[vNow][iRev][1] += df
                vNow = v0

        # フローの増加量を返す
        return df


    numV = len(adjL)
    MaximumFlow = 0
    while True:
        # 残余グラフの始点から終点までの経路（増加パス）を、BFSで探索する
        df = BFS(vSt, vEn)

        if df == 0:
            # 経路が見つからない場合、最大フローの値を返す
            return MaximumFlow

        # フローを加算する
        MaximumFlow += df


N = int(input())
As = list(map(int, input().split()))

adjList = [[] for v in range(N + 2)]
for i, A in enumerate(As, 1):
    if A <= 0:
        addEdge(adjList, 0, i, -A)
    else:
        addEdge(adjList, i, N + 1, A)

for i in range(1, N + 1):
    for j in range(2 * i, N + 1, i):
        addEdge(adjList, i, j, float('inf'))

# Edmonds-Karp法（最大フローを求める）
mf = Edmonds_Karp(adjList, 0, N + 1)
print(sum([A for A in As if A > 0]) - mf)

Submission status: Accepted

Solution code:
# グラフに辺を追加する
def addEdge(adjL, vFr, vTo, cap):
    adjL[vFr].append([vTo, cap, len(adjL[vTo])])
    adjL[vTo].append([vFr, 0, len(adjL[vFr]) - 1]) # 逆辺


# Ford-Fulkerson法（最大フローを求める）
def Ford_Fulkerson(adjL, vSt, vEn):

    # 残余グラフの始点から終点までの経路（増加パス）を、DFSで探索する
    def DFS(vNow, vEn, fNow):
        if vNow == vEn:
            # 終点に到達したら、フローの増加量を返す
            return fNow

        used[vNow] = True

        for i, (v2, cap, iRev) in enumerate(adjL[vNow]):
            if not used[v2] and cap > 0:
                # 未探索の頂点への辺の容量に空きがある場合、探索する
                df = DFS(v2, vEn, min(fNow, cap))
                if df > 0:
                    # 始点から終点までの経路を遡って、辺のフローを変更する
                    adjL[vNow][i][1] -= df
                    adjL[v2][iRev][1] += df
                    return df

        # 現在の頂点からの探索先がない場合、ゼロを返す
        return 0


    numV = len(adjL)
    MaximumFlow = 0
    while True:
        # 残余グラフの始点から終点までの経路（増加パス）を、DFSで探索する
        used = [False] * numV
        df = DFS(vSt, vEn, float('inf'))

        if df == 0:
            # 経路が見つからない場合、最大フローの値を返す
            return MaximumFlow

        # フローを加算する
        MaximumFlow += df


N = int(input())
As = list(map(int, input().split()))

adjList = [[] for v in range(N + 2)]
for i, A in enumerate(As, 1):
    if A <= 0:
        addEdge(adjList, 0, i, -A)
    else:
        addEdge(adjList, i, N + 1, A)

for i in range(1, N + 1):
    for j in range(2 * i, N + 1, i):
        addEdge(adjList, i, j, float('inf'))

# Ford-Fulkerson法（最大フローを求める）
mf = Ford_Fulkerson(adjList, 0, N + 1)
print(sum([A for A in As if A > 0]) - mf)

Submission status: Accepted

Solution code:
import collections
class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in range(n)]
    def add_edge(self, fr, to, cap):
        self.g[fr].append([to, cap, len(self.g[to])])
        self.g[to].append([fr, 0, len(self.g[fr])-1])
    def add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])
    def bfs(self, s):
        level = [-1]*self.n
        deq = collections.deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level
    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in range(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow

N = int(input())
*A, = map(int, input().split())
dinic = Dinic(N+2)

INF = 10**18

su = 0
for x in range(1, N+1):
    a = A[x-1]
    if a > 0:
        su += a
        dinic.add_edge(0, x+1, a)
    elif a < 0:
        dinic.add_edge(x+1, 1, -a)

for x in range(1, N+1):
    for y in range(x+x, N+1, x):
        dinic.add_edge(y+1, x+1, INF)

print(su - dinic.max_flow(0, 1))

Submission status: Accepted

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

from sys import stdin
from fractions import gcd	# math.gcd is introduced in python 3.5
from functools import reduce

def lcm(x, y):
    """The least common multiple of x and y."""
    return x * (y // gcd(x, y))

def multiples(t, N):
    """Set of multiples (<= N) of some x in t."""
    return set(i for x in t for i in range(x, N + 1, x))

def value(a, t):
    """The value of the jewels that are labeled a multiple of some x in t."""
    return sum(a[i - 1] for i in multiples(t, len(a)))

def remove(a, t):
    """Break all jewels that are labeled a multiple of some x in t."""
    for i in multiples(t, len(a)):
        a[i - 1] = 0

def tuples(m, N):
    """
    List of tuples over {m,...,N}.
    Each tuple t in the list satisfies that:
        the lcm of t is less than or equal to N, and
        t does not contain a proper multiple of some j in t.
    """
    if m > N: return [()]
    ts = tuples(m + 1, N)
    us = [(m,) + t for t in ts
          if reduce(lcm, t, m) <= N and all(j % m != 0 for j in t)]
    ts.extend(us)
    return ts

def solve(a):
    N = len(a)
    for t in tuples(1, N):
        if value(a, t) < 0: remove(a, t)
    return sum(a)

N = int(stdin.readline())
a = [int(w) for w in stdin.readline().split()]
if len(a) != N: raise
print(solve(a))

Submission status: Accepted

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

from sys import stdin
from fractions import gcd	# math.gcd is introduced in python 3.5
from functools import reduce

def lcm(x, y):
    """The least common multiple of x and y."""
    return x * (y // gcd(x, y))

def flatten(ls):
    """Flatten a list of lists."""
    return [x for l in ls for x in l]


def multiples(t, N):
    """Set of multiples (<= N) of some x in t."""
    return set(i for x in t for i in range(x, N + 1, x))

def value(a, t):
    """The value of the jewels that are labeled a multiple of some x in t."""
    return sum(a[i - 1] for i in multiples(t, len(a)))

def remove(a, t):
    """Break all jewels that are labeled a multiple of some x in t."""
    for i in multiples(t, len(a)):
        a[i - 1] = 0


def tuples(m, N):
    """
    [[m'-tuples over {1,2,3,...,N}] for 0 <= m' <= m].
    The lcm of the m-tuple is less than or equal to N.
    Each m-tuple does not contain a multiple of some j in the tuple.
    """
    if m == 0: return [[()]]
    ts = tuples(m - 1, N)
    if ts[-1] == []: return ts

    ls = []
    for t in ts[-1]:
        lc = reduce(lcm, t) if len(t) > 0 else 1
        mi = min(t)         if len(t) > 0 else N + 1
        for i in range(mi - 1, 0, -1):
            if lcm(lc, i) > N: continue
            if any(j % i == 0 for j in t): continue
            ls.append((i,) + t)  # smaller label first
    ts.append(ls)
    return ts

def solve(a):
    N = len(a)
    tl = flatten(tuples(N, N))
    # break jewels with larger labels first.
    tl.sort(key=lambda t: [-x for x in t])
    for t in tl:
        if value(a, t) < 0: remove(a, t)
    return sum(a)

N = int(stdin.readline())
a = [int(w) for w in stdin.readline().split()]
if len(a) != N: raise
print(solve(a))

Submission status: Accepted

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

from sys import stdin
from fractions import gcd	# math.gcd is introduced by python 3.5
from functools import reduce

def lcm(x, y):
  """The least common multiple of x and y."""
  return x * (y // gcd(x, y))

def tuples(m, N):
  """
  List of list of m'-tuples over {1,2,3,...,N} for 0 <= m' <= m.
  Every m-tuple does not contain a multiple of some j in the tuple.
  The lcm of the m-tuple is less than or equal to N.
  """
  if m == 0: return [[()]]
  ts = tuples(m - 1, N)
  if len(ts[-1]) == 0: return ts

  ls = []
  for t in ts[-1]:
    lc = reduce(lcm, t) if len(t) > 0 else 1
    mi = min(t)         if len(t) > 0 else N + 1
    for i in range(mi - 1, 0, -1):
      if any(j % i == 0 for j in t): continue
      if lcm(lc, i) > N: continue
      ls.append((i,) + t)
  ts.append(ls)
  return ts

def value(a, t):
  """
  Total value of the jewels that are labeled a multiple of x
  for some x in t.
  """
  used = [False for i in a]
  v = 0
  for x in t:
    for i in range(x - 1, len(a), x):
      if not used[i]:
        v = v + a[i]
        used[i] = True
  return v

def remove(a, t):
  """
  Break all jewels that are labeled a multiple of x for some x in t.
  """
  for x in t:
    for i in range(x - 1, len(a), x):
      a[i] = 0

def flatten(ls):
  """Flatten a list of lists."""
  return [x for l in ls for x in l]

def solve(a):
  n = len(a)
  tl = flatten(tuples(n, n))
  tl.sort(key=lambda t: [-x for x in t])
  for t in tl:
    if value(a, t) < 0: remove(a, t)
  return sum(a)

N = int(stdin.readline())
a = [int(w) for w in stdin.readline().split()]
if len(a) != N: raise
print(solve(a))

Submission status: Accepted

Solution code:
from collections import deque


class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None

    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])

    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth

    def dfs(self, v, t, flow):
        if v == t:
            return flow
        for i, link in enumerate(self.links[v]):
            if i < self.progress[v]:
                continue
            self.progress[v] = i
            cap, to, rev = link
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))


n = int(input())
an = list(map(int, input().split()))
mf = Dinic(n + 2)
max_value = 0
for i, a in enumerate(an):
    i += 1
    if a > 0:
        max_value += a
        mf.add_link(i, n + 1, a)
    else:
        mf.add_link(0, i, -a)
    for j in range(2 * i, n + 1, i):
        mf.add_link(i, j, float('inf'))
print(max_value - mf.max_flow(0, n + 1))

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--

INF = float('inf');

def fulkerson(graph, src, sink):
    n = len(graph)

    matrix = [[0]*n for i in range(n)]
    bothDirGraph = [[] for i in range(n)]

    for nodeId, edges in enumerate(graph):
        for nodeId2, flowLimit in edges:
            matrix[nodeId][nodeId2] = flowLimit
            bothDirGraph[nodeId].append(nodeId2)
            bothDirGraph[nodeId2].append(nodeId)

    while True:
        path = findPath(bothDirGraph, matrix, src, sink)

        if path == None:
            break

        v = min(matrix[path[i]][path[i+1]] 
                for i in range(len(path)-1))

        for i in range(len(path)-1):
            node1 = path[i]
            node2 = path[i+1]
            
            matrix[node1][node2] -= v
            matrix[node2][node1] += v

    return (sum(c for _, c in graph[src]) - 
            sum(c for c in matrix[src]))


def findPath(bothDirGraph, matrix, src, sink):
    prevs = [None]*len(matrix)
    q = set([src])
    prevs[src] = src

    while len(q) > 0:
        node = q.pop()

        for nextNode in bothDirGraph[node]:
            if prevs[nextNode] == None and matrix[node][nextNode] > 0:
                prevs[nextNode] = node
                
                if nextNode == sink:
                    path = []
                    pathNode = sink

                    while pathNode != src:
                        path.append(pathNode)
                        pathNode = prevs[pathNode]

                    path.append(src)
                    return list(reversed(path))

                q.add(nextNode)

    return None
                    
def f(N, A):
    graph = [[] for i in range(N+2)]
    srcId = 0
    dstId = N+1

    for nodeId, a in enumerate(A, 1):
        if a < 0:
            graph[0].append((nodeId, -a))
        else:
            graph[nodeId].append((N+1, a))

        for k in range(2, N//nodeId+1):
            graph[nodeId].append((nodeId*k, INF))

    return (sum(filter(lambda a: a>0, A)) - 
            fulkerson(graph, 0, N+1))

def main():
    N = int(input())
    A = list(map(int, input().split()))

    print(f(N, A))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))

def func(Bs):
    for x in range(N):
        if Bs[x] >= 0: continue
        if max(Bs[x::x + 1]) <= 0:
            Bs[x] = 0

func(As)

zs = [27, 29, 31, 33] + list(range(34, 51))
for x in zs:
    if sum(As[x - 1::x]) < 0:
        for i in range(x - 1, N, x):
            As[i] = 0

ns = [1, 2, 4, 8, 16, 32] + [3, 6, 9, 12, 18, 24, 27, 36, 48] \
    + [5, 10, 15, 20, 25, 30, 40, 45, 50] + [7, 14, 21, 28, 35, 42, 49] \
    + [11, 22, 33, 44] + [13, 26, 39] + [17, 34] + [19, 38] + [23, 46] \
    + [29, 31, 37, 41, 43, 47]

memo = {}
memo[tuple(As)] = sum(As)

cs = [n - 1 for n in ns if n <= N and n not in zs and As[n - 1] < 0]
for c in cs:
    for tupleA in list(memo.keys()):
        if tupleA[c] == 0:
            continue

        listA = list(tupleA)
        for x in range(c, N, c + 1):
            listA[x] = 0

        func(listA)
        memo[tuple(listA)] = sum(listA)

print(max(memo.values()))

Submission status: Accepted

Solution code:
class Ford_Fulkerson:

	def __init__(self, v, inf=float("inf")):
		self.V = v
		self.inf = inf
		self.G = [[] for _ in range(v)]
		self.used = [False for _ in range(v)]

	def addEdge(self, fm, to, cap):
		'''
		to:行き先
		cap:容量
		rev:反対側の辺
		'''
		self.G[fm].append({'to':to, 'cap':cap, 'rev':len(self.G[to])})
		self.G[to].append({'to':fm, 'cap':0, 'rev':len(self.G[fm])-1})


	def dfs(self, v, t, f):
		if v == t: return f
		self.used[v] = True

		for i in range(len(self.G[v])):
			e = self.G[v][i]
			if self.used[e["to"]] != True and e['cap'] > 0:
				d = self.dfs(e['to'], t ,min(f, e['cap']))
				if d > 0:
					e['cap'] -= d
					self.G[e['to']][e['rev']]['cap'] += d
					return d
		return 0

	def max_flow(self,s,t):
		flow = 0
		while True:
			self.used = [False for i in range(self.V)]
			f = self.dfs(s,t,self.inf)
			if f == 0: return flow
			flow += f



from sys import stdin, setrecursionlimit
def IL():return list(map(int, stdin.readline().split()))
 
setrecursionlimit(1000000)

def main():
	N = int(input())
	a = IL()
	d = Ford_Fulkerson(N+2)
	res = 0
	for i in range(N):
	    d.addEdge(N,i, max(0, -a[i]))
	    d.addEdge(i,N+1, max(0,a[i]))
	    res+=max(0,a[i])
	    t = 2*i+2
	    while t<=N:
	        d.addEdge(i,t-1,float('inf'))
	        t+=i+1
	print(res-d.max_flow(N,N+1))
	
	
if __name__ == "__main__": main()

Submission status: Accepted

Solution code:
class Dinic:

	def __init__(self, v, inf=float("inf")):
		self.V = v
		self.inf = inf
		self.G = [[] for _ in range(v)]
		self.level = [0 for _ in range(v)]
		self.iter = [0 for _ in range(v)]

	def addEdge(self, fm, to, cap):
		'''
		to:行き先
		cap:容量
		rev:反対側の辺
		'''
		self.G[fm].append({'to':to, 'cap':cap, 'rev':len(self.G[to])})
		self.G[to].append({'to':fm, 'cap':0, 'rev':len(self.G[fm])-1})


	# sからの最短距離をbfsで計算
	def bfs(self, s):
		import queue
		self.level = [-1 for _ in range(self.V)]
		self.level[s] = 0
		que = queue.Queue()
		que.put(s)

		while not que.empty():
			v = que.get()
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if e['cap'] > 0 and self.level[e['to']] < 0:
					self.level[e['to']] = self.level[v] + 1
					que.put(e['to'])


	def dfs(self, v, t, f):
		if v == t: return f
		for i in range(self.iter[v], len(self.G[v])):
			self.iter[v] = i
			e = self.G[v][i]
			if e['cap'] > 0 and self.level[v] < self.level[e['to']]:
				d = self.dfs(e['to'], t ,min(f,e['cap']))
				if d > 0:
					e['cap'] -= d
					self.G[e['to']][e['rev']]['cap'] += d
					return d
		return 0


	def max_flow(self,s,t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] < 0: return flow
			self.iter = [0 for _ in range(self.V)]
			f = self.dfs(s,t,self.inf)
			while f > 0:
				flow += f
				f = self.dfs(s,t,self.inf)



from sys import stdin, setrecursionlimit
def IL():return list(map(int, stdin.readline().split()))
 
setrecursionlimit(1000000)

def main():
	N = int(input())
	a = IL()
	d = Dinic(N+2)
	res = 0
	for i in range(N):
	    d.addEdge(N,i, max(0, -a[i]))
	    d.addEdge(i,N+1, max(0,a[i]))
	    res+=max(0,a[i])
	    t = 2*i+2
	    while t<=N:
	        d.addEdge(i,t-1,float('inf'))
	        t+=i+1
	print(res-d.max_flow(N,N+1))
	
	
if __name__ == "__main__": main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def divisions(n):
    sq = int(math.sqrt(n)+1)
    d = collections.defaultdict(int)
    while n % 2 == 0:
        n //= 2
        d[2] += 1
    i = 3
    while n > 1 and sq >= i:
        if n % i == 0:
            n //= i
            d[i] += 1
        else:
            i += 2

    if n > 1:
        d[n] += 1

    r = [1]
    for k, v in d.items():
        for c in r[:]:
            for i in range(1,v+1):
                r.append(c*(k**i))

    return sorted(r)

def main():
    n = I()
    a = LI()
    s = set()
    for i in range(n,0,-1):
        d = divisions(i)
        ld = len(d)
        for j in range(1,2**ld):
            c = []
            ff = True
            for k in range(ld):
                if j & (1<<k):
                    f = True
                    for e in c:
                        if d[k] % e == 0:
                            f = False
                            ff = False
                            break
                    if f:
                        c.append(d[k])
                if not ff:
                    break
            if ff:
                s.add(tuple(c + [n+1]))
    b = sorted(list(s), reverse=True)
    for c in b:
        t = 0
        for j in range(1,n+1):
            f = False
            for e in c:
                if j%e == 0:
                    f = True
                    break
            if f:
                t += a[j-1]
        if t < 0:
            for j in range(1,n+1):
                f = False
                for e in c:
                    if j%e == 0:
                        f = True
                        break
                if f:
                    a[j-1] = 0

    return sum(a)



print(main())

Submission status: Accepted

Solution code:
n = int(input())
a = [0] + list(map(int, input().split()))
alive = [1 for i in range(n + 1)]
sol = sum(a)
while True:
    pot = []
    change = False
    for i in range(n, 0, -1):
        if a[i] >= 0 or alive[i] == 0:
            continue
        saldo = 0
        j = i
        while j <= n:
            saldo += alive[j] * a[j]
            j += i
        if saldo > 0:
            pot.append(i)
            continue
        change = True
        sol -= saldo
        j = i
        while j <= n:
            alive[j] = 0
            j += i
    if change:
        continue
    k = len(pot)
    for i in range(k):
        if change: break
        for j in range(i):
            saldo = 0
            for v in range(1, n + 1):
                if v % pot[i] == 0 or v % pot[j] == 0:
                    saldo += alive[v] * a[v]
            if saldo <= 0:
                change = True
                sol -= saldo
                for v in range(1, n + 1):
                    if v % pot[i] == 0 or v % pot[j] == 0:
                        alive[v] = 0
                break
    if not change:
        break
print(sol)

Submission status: Runtime Error

Solution code:
from collections import deque
class Dinic:
    def __init__(self, N):
        elf.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow



import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
a = list( map(int, input().split()))

score = 0
INF = float('inf')
graph = Dinic(n+2)

for i in range(n):
    if a[i]>0:
        graph.add_edge(i+1,n+1,a[i])
        score += a[i]
    elif a[i]<0:
        graph.add_edge(0,i+1,-a[i])

for i in range(1,n//2+1):
    for j in range(2*i,n+1,i):
        graph.add_edge(i,j,INF)

print(score-graph.flow(0,n+1))

Submission status: Runtime Error

Solution code:
¥from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

class Dinic():
    def __init__(self, source, sink):
        self.G = defaultdict(lambda:defaultdict(int))
        self.sink = sink
        self.source = source

    def add_edge(self, u, v, cap):
        self.G[u][v] = cap
        self.G[v][u] = 0

    def bfs(self):
        level = defaultdict(int)
        q = [self.source]
        level[self.source] = 1
        d = 1
        while q:
            if level[self.sink]:
                break
            qq = []
            d += 1
            for u in q:
                for v, cap in self.G[u].items():
                    if cap == 0:
                        continue
                    if level[v]:
                        continue
                    level[v] = d
                    qq += [v]
            q = qq
        self.level = level

    def dfs(self, u, f):
        if u == self.sink:
            return f
        for v, cap in self.iter[u]:
            if cap == 0 or self.level[v] != self.level[u] + 1:
                continue
            d = self.dfs(v, min(f, cap))
            if d:
                self.G[u][v] -= d
                self.G[v][u] += d
                return d
        return 0

    def max_flow(self):
        flow = 0
        while True:
            self.bfs()
            if self.level[self.sink] == 0:
                break
            self.iter = {u: iter(self.G[u].items()) for u in self.G}
            while True:
                f = self.dfs(self.source, INF)
                if f == 0:
                    break
                flow += f
        return flow

n = I()
A = LI()
score = 0
s = 0
t = n + 1
dinic = Dinic(s, t)
for i in range(1, n + 1):
    if A[i - 1] > 0:
        score += A[i - 1]
        dinic.add_edge(s, i, 0)
        dinic.add_edge(i, t, A[i - 1])
    else:
        dinic.add_edge(s, i, -A[i - 1])
        dinic.add_edge(i, t, 0)
    ret = i * 2
    while ret <= n:
        dinic.add_edge(i, ret, INF)
        ret += i

print(score - dinic.max_flow())

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;

#if defined(DEBUG)

#include <unistd.h>
#include <sys/fcntl.h>
#define DLOG(...)        cerr << dbgFormat(__VA_ARGS__) << endl
#define DCALL(func, ...) func(__VA_ARGS__)

template <class... Args>
string dbgFormat(const char* fmt, Args... args) {
  size_t len = snprintf(nullptr, 0, fmt, args...);
  char buf[len + 1];
  snprintf(buf, len + 1, fmt, args...);
  return string(buf);
}

#else  // defined(DEBUG)

#define DLOG(...)
#define DCALL(func, ...)

#endif // defined(DEBUG)
// ----------------------------------------------------------------------

struct Edge {
  int dst;
  ll cap;
  int rev;
  Edge(int d, ll c, int r) : dst(d), cap(c), rev(r) {}
};

class Dinic {

  int vSize;
  int source;
  int sink;
  vector<int> level;  // from sink rather than source
  vector<size_t> iter;
  vector<vector<Edge>> edges;

  ll dfs(int u, ll sCap) {
    if (u == sink) return sCap;
    ll f = 0;
    for (size_t& i = iter.at(u); i < edges.at(u).size(); i++) {
      Edge& e = edges.at(u).at(i);
      if (e.cap == 0 || level.at(e.dst) >= level.at(u)) continue;
      ll f0 = dfs(e.dst, min(sCap - f, e.cap));
      e.cap -= f0;
      edges.at(e.dst).at(e.rev).cap += f0;
      f += f0;
      if (f == sCap) break;
    }
    return f;
  }

  void set_level() {
    level.assign(vSize, -1);
    deque<pair<int,int>> deq;
    deq.emplace_back(sink, 0);
    while (!deq.empty()) {
      pair<int,int> p = deq.front(); deq.pop_front();
      int i = p.first;
      int lev = p.second;
      if (level.at(i) >= 0) continue;
      level.at(i) = lev;
      for (const Edge& erev : edges.at(i)) {
	const Edge& e = edges.at(erev.dst).at(erev.rev);
	if (e.cap == 0) continue;
	deq.emplace_back(erev.dst, lev + 1);
      }
    }
  }

public:

  Dinic(int sz, int src, int snk)
    : vSize(sz), source(src), sink(snk), edges(sz) {}

  void add_edge(int u, int v, ll cap) {
    assert(0 <= u && u < vSize && 0 <= v && v < vSize);
    assert(cap > 0);
    int nu = edges.at(u).size();
    int nv = edges.at(v).size();
    edges.at(u).push_back(Edge(v, cap, nv));
    edges.at(v).push_back(Edge(u, 0,   nu));
  }

  ll run() {
    ll flow = 0;
    while(1) {
      set_level();
      if (level.at(source) == -1) break;
      iter.assign(vSize, 0);
      flow += dfs(source, LLONG_MAX);
    }
    return flow;
  }
};

// ----------------------------------------------------------------------
int main(int argc, char *argv[]) {
#if defined(DEBUG)
  // GDB on Cygwin ignores redirection at run command.
  if (argc == 2) dup2(open(argv[1], 0), 0);
#else
  // For performance.  We should not use C-style stdio functions
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cout << setprecision(20);

  int N; cin >> N;

  ll myINF = (ll)1e16;

  ll pos = 0;
  Dinic g(N+2, 0, N+1);
  for (int i = 1; i <= N; i++) {
    ll a; cin >> a;
    if (a < 0) g.add_edge(0, i, -a);
    else {
      g.add_edge(i, N+1, a);
      pos += a;
    }
  }
  for (int i = 1; i <= N; i++) {
    for (int j = 2; j <= N && i*j <= N; j++) {
      g.add_edge(i, i*j, myINF);
    }
  }
  ll flow = g.run();
  cout << pos - flow << endl;

  return 0;
}